在平時(shí)工作中，接觸到的數(shù)據(jù)庫(kù)最多的就是Mysql數(shù)據(jù)庫(kù)了集币，mysql數(shù)據(jù)庫(kù)它的開源免費(fèi)特性以及支持百萬級(jí)存儲(chǔ)性能奉瘤，受到許多中小公司的青睞卡骂，甚至是阿里這樣的巨頭都在使用国裳，基本大部分開發(fā)人員第一次接觸的也都是基于Mysql作為底層數(shù)據(jù)的存儲(chǔ)，來入門web軟件開發(fā)全跨，CRUD用的很多缝左，復(fù)雜的多表查詢，各種內(nèi)外連接浓若，以及子查詢和group by 等操作渺杉，但是只知其一不知其二，本著知其然挪钓，也要知其所以然的態(tài)度是越，本篇文章來記錄研究下mysql內(nèi)部理論和實(shí)現(xiàn)機(jī)制。
無數(shù)據(jù)庫(kù)實(shí)現(xiàn)快速查詢
思考一個(gè)問題碌上，當(dāng)早期沒有數(shù)據(jù)庫(kù)的時(shí)候倚评，如何快速的查詢數(shù)據(jù)呢浦徊，這里如果讓你來設(shè)計(jì)實(shí)現(xiàn)一個(gè)系統(tǒng)，如何能夠快速的檢索到保存的數(shù)據(jù)呢天梧。生活中盔性，當(dāng)我們思索解決問題的方式的時(shí)候，通常會(huì)尋找出一個(gè)熟悉的事物去套,這里我們舉個(gè)生活中的例子呢岗，比如一個(gè)我們從一本書中要快速找到想看的章節(jié)冕香，我們是怎么做的呢？我們的做法是首先翻到目錄頁后豫，然后找到目錄頁內(nèi)容悉尾，最后找到感興趣的想看的后，根據(jù)目錄頁面的頁碼挫酿，就可以很快找到了构眯。這里的目錄其實(shí)就是類比數(shù)據(jù)庫(kù)的索引，所以我們高效快速找到想要的數(shù)據(jù)饭豹。這里就分析得出一個(gè)結(jié)論鸵赖，索引能夠快速的提高數(shù)據(jù)的查詢务漩。
如果不用數(shù)據(jù)庫(kù)來查詢拄衰，那么可以通過將數(shù)據(jù)文件寫入本地或者網(wǎng)絡(luò)上其他機(jī)器，文件類型可以是自定義格式饵骨，或者用excel 表格翘悉，數(shù)據(jù)庫(kù)也是解決數(shù)據(jù)存儲(chǔ)和計(jì)算的服務(wù)器，這樣如何解決查詢的問題居触，基本就需要根據(jù)文件格式來定義妖混，這樣存在一個(gè)問題就是，查詢方式不能夠統(tǒng)一轮洋。這里我們?nèi)绻胑xcel表格來存儲(chǔ)數(shù)據(jù)制市，那么我們將第一行做為表格頭，這里表格頭是作為數(shù)據(jù)列字段弊予，那么查詢的時(shí)候祥楣，比如我們要查詢下圖中的學(xué)號(hào)為3的學(xué)生，那么必須定位到C列才行汉柒，然后將該列處了C1以外的數(shù)據(jù)全部檢索出來误褪，然后通過程序?qū)?shù)據(jù)讀取到內(nèi)存中，然后再找到其中的學(xué)好為3的王五碾褂。這里就涉及到全文檢索兽间，這里舉例中只有三條數(shù)據(jù)，并且每條記錄字段只有3個(gè)正塌，分別是姓名嘀略，年齡恤溶，學(xué)號(hào)，如果是更多呢帜羊，一億條呢宏娄？那么將對(duì)我們的內(nèi)存是個(gè)極大的挑戰(zhàn)，所以這里我們需要建立索引逮壁，通過索引來快速定位到要查詢的數(shù)據(jù)孵坚，而不是輪詢。
這里我們就需要根據(jù)學(xué)號(hào)來建立一個(gè)索引窥淆，把學(xué)號(hào)作為key,其他的字段作為value卖宠，來存儲(chǔ)，當(dāng)我們下次再找到學(xué)號(hào)為3的時(shí)候忧饭，可以直接快速查找到學(xué)號(hào)為3的王五扛伍。
那么如何去存儲(chǔ)呢？一個(gè)良好的設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)可以很快的解決遇到的難題词裤。學(xué)過的數(shù)據(jù)結(jié)構(gòu)有刺洒，數(shù)組，鏈表吼砂，有Map結(jié)構(gòu)等逆航，分別對(duì)應(yīng)集合，線性結(jié)構(gòu)渔肩，樹形結(jié)構(gòu)因俐，圖形結(jié)構(gòu)。
樹形結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在一對(duì)多的相互關(guān)系
圖形結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在多對(duì)多的相互關(guān)系
數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)周偎、組織數(shù)據(jù)的方式抹剩。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。通常情況下蓉坎，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運(yùn)行或者存儲(chǔ)效率澳眷。數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)。
重點(diǎn)關(guān)注的是樹形結(jié)構(gòu)蛉艾，在從一堆數(shù)據(jù)中查找指定的數(shù)據(jù)時(shí)钳踊，我們常用的數(shù)據(jù)結(jié)構(gòu)是哈希表和二叉查找樹，表本質(zhì)上就是一堆數(shù)據(jù)的集合伺通，所以MySQL數(shù)據(jù)庫(kù)用了哈希表和B+樹來實(shí)現(xiàn)索引
二叉查找樹
二叉查找樹是帶有特殊屬性的二叉樹箍土，需要滿足以下屬性
非葉子節(jié)點(diǎn)最多擁有兩個(gè)子節(jié)點(diǎn)
非葉子節(jié)值大于左邊子節(jié)點(diǎn)、小于右邊子節(jié)點(diǎn)（左小右大）
沒有值相等重復(fù)的節(jié)點(diǎn);
首先罐监，讓我們看下這個(gè)圖
從圖中可以看出吴藻，user表有id 和name 兩個(gè)字段，右邊的是二叉樹索引的構(gòu)建圖弓柱，最上層是根節(jié)點(diǎn)沟堡，根節(jié)點(diǎn)上10是存儲(chǔ)的鍵值侧但，這里id就是key值，那么這個(gè)樹的構(gòu)成因?yàn)槎鏄涞男再|(zhì)航罗，"左小又大",那么id為7禀横，name是ls的用戶就應(yīng)該放在10的左邊，id是13的節(jié)點(diǎn)粥血，name為ww的用戶就在根節(jié)點(diǎn)的又邊柏锄。
圖中的圓為二叉查找樹的節(jié)點(diǎn)，節(jié)點(diǎn)中存儲(chǔ)了鍵（key）和數(shù)據(jù)（data）复亏。鍵對(duì)應(yīng) user 表中的 id趾娃，數(shù)據(jù)對(duì)應(yīng) user 表中的行數(shù)據(jù)。
二叉查找樹的特點(diǎn)就是任何節(jié)點(diǎn)的左子節(jié)點(diǎn)的鍵值都小于當(dāng)前節(jié)點(diǎn)的鍵值缔御，右子節(jié)點(diǎn)的鍵值都大于當(dāng)前節(jié)點(diǎn)的鍵值抬闷。頂端的節(jié)點(diǎn)我們稱為根節(jié)點(diǎn)，沒有子節(jié)點(diǎn)的節(jié)點(diǎn)我們稱之為葉節(jié)點(diǎn)耕突。
如果我們需要查找 id=12 的用戶信息笤成，利用我們創(chuàng)建的二叉查找樹索引，查找流程如下：
將根節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)眷茁，把 12 與當(dāng)前節(jié)點(diǎn)的鍵值 10 比較炕泳，12 大于 10，接下來我們把當(dāng)前節(jié)點(diǎn)>的右子節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)蔼卡。
繼續(xù)把 12 和當(dāng)前節(jié)點(diǎn)的鍵值 13 比較喊崖，發(fā)現(xiàn) 12 小于 13挣磨，把當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)雇逞。
-
把 12 和當(dāng)前節(jié)點(diǎn)的鍵值 12 對(duì)比，12 等于 12茁裙，滿足條件塘砸，我們從當(dāng)前節(jié)點(diǎn)中取出 data，即 id=12晤锥，name=xm掉蔬。
利用二叉查找樹我們只需要 3 次即可找到匹配的數(shù)據(jù)。如果在表中一條條的查找的話矾瘾，我們需要 6 次才能找到女轿。
平衡二叉樹
上面我們講解了二叉樹查找的過程，利用二叉查找樹可以快速的查詢到數(shù)據(jù)壕翩，但是假如有這樣一條特例蛉迹，如下圖所示：
這個(gè)時(shí)候，我們看到二叉查找樹變成了一個(gè)鏈表結(jié)構(gòu)放妈，如果我們要查找到id值為17的節(jié)點(diǎn)北救，那么我們需要查找7次荐操，就相當(dāng)于全表掃描。導(dǎo)致這個(gè)現(xiàn)象的原因就是因?yàn)檫@個(gè)二叉樹不是傳統(tǒng)的二叉樹珍策，從圖中看出來就怪異托启，也就是變的不平衡了，這個(gè)層級(jí)有7層攘宙，從而導(dǎo)致查找的效率不穩(wěn)定屯耸。為了解決這個(gè)問題，我們需要一個(gè)平衡的二叉樹蹭劈。平衡二叉樹又叫AVl樹肩民，在滿足二叉查找樹特性的基礎(chǔ)上，要求每個(gè)節(jié)點(diǎn)的左右子樹的高度差不能超過 1链方。
由平衡二叉樹的構(gòu)造我們可以發(fā)現(xiàn)第一張圖中的二叉樹其實(shí)就是一棵平衡二叉樹持痰。
平衡二叉樹保證了樹的構(gòu)造是平衡的，當(dāng)我們插入或刪除數(shù)據(jù)導(dǎo)致不滿足平衡二叉樹不平衡時(shí)祟蚀，平衡二叉樹會(huì)進(jìn)行調(diào)整樹上的節(jié)點(diǎn)來保持平衡工窍。具體的調(diào)整方式這里就不介紹了。平衡二叉樹相比于二叉查找樹來說前酿，查找效率更穩(wěn)定患雏，總體的查找速度也更快。
B 樹
當(dāng)我們平時(shí)在使用內(nèi)存的時(shí)候罢维，由于內(nèi)存中的存儲(chǔ)的數(shù)據(jù)在斷電的時(shí)候淹仑，容易丟失，所以我們基本都會(huì)將數(shù)據(jù)存儲(chǔ)在磁盤這種外圍設(shè)備上肺孵，比如將這里的user表中的數(shù)據(jù)和索引存儲(chǔ)匀借。但是和內(nèi)存相比，從磁盤上讀取數(shù)據(jù)的速度就要相對(duì)慢很多平窘，所以我們應(yīng)當(dāng)盡量減少?gòu)拇疟P讀取的次數(shù)吓肋，并且我們平時(shí)從磁盤中讀取數(shù)據(jù)，都是按照磁盤塊來讀取的瑰艘，并不是一條一條來讀的是鬼。如果我們有大量的數(shù)據(jù)已經(jīng)存儲(chǔ)在磁盤上，那一次磁盤讀取操作就會(huì)讀取更多數(shù)據(jù)紫新，從而我們查找數(shù)據(jù)的時(shí)間也會(huì)大幅度降低均蜜。如果我們用平衡二叉樹來查找數(shù)據(jù)，平衡二叉樹可是每個(gè)節(jié)點(diǎn)只存儲(chǔ)一個(gè)鍵值和數(shù)據(jù)的芒率，那么我們每次讀取一個(gè)節(jié)點(diǎn)的數(shù)據(jù)都要從磁盤塊中獲取一次囤耳，如果有大量的數(shù)據(jù)要讀取呢，豈不是每次讀取一個(gè)節(jié)點(diǎn)數(shù)據(jù)就得去磁盤塊中找一次，可以想象到二叉樹的節(jié)點(diǎn)將會(huì)非常多紫皇，高度也會(huì)極其高慰安，我們查找數(shù)據(jù)時(shí)也會(huì)進(jìn)行很多次磁盤 IO，我們查找數(shù)據(jù)的效率將會(huì)極低聪铺。
為了解決平衡二叉樹的這個(gè)弊端化焕，我們應(yīng)該尋找一種單個(gè)節(jié)點(diǎn)可以存儲(chǔ)多個(gè)鍵值和數(shù)據(jù)的平衡樹。也就是我們接下來要說的 B 樹铃剔。
B 樹（Balance Tree）即為平衡樹的意思撒桨，下圖即是一棵 B 樹
圖中的 p 節(jié)點(diǎn)為指向子節(jié)點(diǎn)的指針，二叉查找樹和平衡二叉樹其實(shí)也有键兜，因?yàn)閳D的美觀性凤类，被省略了。
圖中的每個(gè)節(jié)點(diǎn)稱為頁普气，頁就是我們上面說的磁盤塊谜疤，在 MySQL 中數(shù)據(jù)讀取的基本單位都是頁，所以我們這里叫做頁更符合 MySQL 中索引的底層數(shù)據(jù)結(jié)構(gòu)现诀。
從上圖可以看出夷磕，B 樹相對(duì)于平衡二叉樹，每個(gè)節(jié)點(diǎn)存儲(chǔ)了更多的鍵值（key）和數(shù)據(jù)（data）仔沿，并且每個(gè)節(jié)點(diǎn)擁有更多的子節(jié)點(diǎn)坐桩，子節(jié)點(diǎn)的個(gè)數(shù)一般稱為階，上述圖中的 B 樹為 3 階 B 樹封锉，高度也會(huì)很低绵跷。
基于這個(gè)特性，B 樹查找數(shù)據(jù)讀取磁盤的次數(shù)將會(huì)很少成福，數(shù)據(jù)的查找效率也會(huì)比平衡二叉樹高很多碾局。
假如我們要查找 id=28 的用戶信息，那么我們?cè)谏蠄D B 樹中查找的流程如下：
- 先找到根節(jié)點(diǎn)也就是頁 1闷叉，判斷 28 在鍵值 17 和 35 之間擦俐，那么我們根據(jù)頁 1 中的指針 p2 找到頁 3。
- 將 28 和頁 3 中的鍵值相比較握侧，28 在 26 和 30 之間，我們根據(jù)頁 3 中的指針 p2 找到頁 8嘿期。
- 將 28 和頁 8 中的鍵值相比較品擎，發(fā)現(xiàn)有匹配的鍵值 28，鍵值 28 對(duì)應(yīng)的用戶信息為（28备徐，bv）萄传。
B+ 樹
B+ 樹是對(duì) B 樹的進(jìn)一步優(yōu)化。讓我們先來看下 B+ 樹的結(jié)構(gòu)圖：
根據(jù)上圖我們來看下 B+ 樹和 B 樹有什么不同：
B+ 樹非葉子節(jié)點(diǎn)上是不存儲(chǔ)數(shù)據(jù)的，僅存儲(chǔ)鍵值秀菱，而 B 樹節(jié)點(diǎn)中不僅存儲(chǔ)鍵值振诬，也會(huì)存儲(chǔ)數(shù)據(jù)。 之所以這么做是因?yàn)樵跀?shù)據(jù)庫(kù)中頁的大小是固定的衍菱，InnoDB 中頁的默認(rèn)大小是 16KB赶么。如果不存儲(chǔ)數(shù)據(jù)，那么就會(huì)存儲(chǔ)更多的鍵值脊串，相應(yīng)的樹的階數(shù)（節(jié)點(diǎn)的子節(jié)點(diǎn)樹）就會(huì)更大辫呻，樹就會(huì)更矮更胖，如此一來我們查找數(shù)據(jù)進(jìn)行磁盤的 IO 次數(shù)又會(huì)再次減少琼锋，數(shù)據(jù)查詢的效率也會(huì)更快放闺。另外，B+ 樹的階數(shù)是等于鍵值的數(shù)量的缕坎，如果我們的 B+ 樹一個(gè)節(jié)點(diǎn)可以存儲(chǔ) 1000 個(gè)鍵值怖侦，那么 3 層 B+ 樹可以存儲(chǔ) 1000×1000×1000=10 億個(gè)數(shù)據(jù)。一般根節(jié)點(diǎn)是常駐內(nèi)存的谜叹，所以一般我們查找 10 億數(shù)據(jù)础钠，只需要 2 次磁盤 IO。
因?yàn)?B+ 樹索引的所有數(shù)據(jù)均存儲(chǔ)在葉子節(jié)點(diǎn)叉谜，而且數(shù)據(jù)是按照順序排列的旗吁。那么 B+ 樹使得范圍查找，排序查找停局，分組查找以及去重查找變得異常簡(jiǎn)單很钓。而 B 樹因?yàn)閿?shù)據(jù)分散在各個(gè)節(jié)點(diǎn)，要實(shí)現(xiàn)這一點(diǎn)是很不容易的董栽。有心的讀者可能還發(fā)現(xiàn)上圖 B+ 樹中各個(gè)頁之間是通過雙向鏈表連接的码倦，葉子節(jié)點(diǎn)中的數(shù)據(jù)是通過單向鏈表連接的。其實(shí)上面的 B 樹我們也可以對(duì)各個(gè)節(jié)點(diǎn)加上鏈表锭碳。這些不是它們之前的區(qū)別袁稽，是因?yàn)樵?MySQL 的 InnoDB 存儲(chǔ)引擎中，索引就是這樣存儲(chǔ)的擒抛。也就是說上圖中的 B+ 樹索引就是 InnoDB 中 B+ 樹索引真正的實(shí)現(xiàn)方式推汽，準(zhǔn)確的說應(yīng)該是聚集索引（聚集索引和非聚集索引下面會(huì)講到）。通過上圖可以看到歧沪，在 InnoDB 中歹撒，我們通過數(shù)據(jù)頁之間通過雙向鏈表連接以及葉子節(jié)點(diǎn)中數(shù)據(jù)之間通過單向鏈表連接的方式可以找到表中所有的數(shù)據(jù)。MyISAM 中的 B+ 樹索引實(shí)現(xiàn)與 InnoDB 中的略有不同诊胞。在 MyISAM 中暖夭，B+ 樹索引的葉子節(jié)點(diǎn)并不存儲(chǔ)數(shù)據(jù)，而是存儲(chǔ)數(shù)據(jù)的文件地址。
聚集索引 VS 非聚集索引
在上節(jié)介紹 B+ 樹索引的時(shí)候迈着，我們提到了圖中的索引其實(shí)是聚集索引的實(shí)現(xiàn)方式竭望。
那什么是聚集索引呢？在 MySQL 中裕菠，B+ 樹索引按照存儲(chǔ)方式的不同分為聚集索引和非聚集索引咬清。
這里我們著重介紹 InnoDB 中的聚集索引和非聚集索引：
聚集索引（聚簇索引）：以 InnoDB 作為存儲(chǔ)引擎的表，表中的數(shù)據(jù)都會(huì)有一個(gè)主鍵糕韧，即使你不創(chuàng)建主鍵枫振，系統(tǒng)也會(huì)幫你創(chuàng)建一個(gè)隱式的主鍵。這是因?yàn)?InnoDB 是把數(shù)據(jù)存放在 B+ 樹中的萤彩，而 B+ 樹的鍵值就是主鍵粪滤，在 B+ 樹的葉子節(jié)點(diǎn)中，存儲(chǔ)了表中所有的數(shù)據(jù)雀扶。這種以主鍵作為 B+ 樹索引的鍵值而構(gòu)建的 B+ 樹索引杖小，我們稱之為聚集索引。
非聚集索引（非聚簇索引）：以主鍵以外的列值作為鍵值構(gòu)建的 B+ 樹索引愚墓，我們稱之為非聚集索引予权。非聚集索引與聚集索引的區(qū)別在于非聚集索引的葉子節(jié)點(diǎn)不存儲(chǔ)表中的數(shù)據(jù)，而是存儲(chǔ)該列對(duì)應(yīng)的主鍵浪册，想要查找數(shù)據(jù)我們還需要根據(jù)主鍵再去聚集索引中進(jìn)行查找扫腺，這個(gè)再根據(jù)聚集索引查找數(shù)據(jù)的過程，我們稱為回表村象。明白了聚集索引和非聚集索引的定義笆环，我們應(yīng)該明白這樣一句話：數(shù)據(jù)即索引，索引即數(shù)據(jù)厚者。
利用聚集索引和非聚集索引查找數(shù)據(jù)
前面我們講解 B+ 樹索引的時(shí)候并沒有去說怎么在 B+ 樹中進(jìn)行數(shù)據(jù)的查找躁劣，主要就是因?yàn)檫€沒有引出聚集索引和非聚集索引的概念。
下面我們通過講解如何通過聚集索引以及非聚集索引查找數(shù)據(jù)表中數(shù)據(jù)的方式介紹一下 B+ 樹索引查找數(shù)據(jù)方法库菲。
還是這張 B+ 樹索引圖账忘，現(xiàn)在我們應(yīng)該知道這就是聚集索引，表中的數(shù)據(jù)存儲(chǔ)在其中熙宇。
現(xiàn)在假設(shè)我們要查找 id>=18 并且 id<40 的用戶數(shù)據(jù)鳖擒。對(duì)應(yīng)的 sql 語句為：
select * from user where id>=18 and id <40
其中 id 為主鍵，具體的查找過程如下：
一般根節(jié)點(diǎn)都是常駐內(nèi)存的奇颠，也就是說頁 1 已經(jīng)在內(nèi)存中了败去，此時(shí)不需要到磁盤中讀取數(shù)據(jù)，直接從內(nèi)存中讀取即可烈拒。從內(nèi)存中讀取到頁 1，要查找這個(gè) id>=18 and id <40 或者范圍值，我們首先需要找到 id=18 的鍵值荆几。從頁 1 中我們可以找到鍵值 18吓妆，此時(shí)我們需要根據(jù)指針 p2，定位到頁 3吨铸。
要從頁 3 中查找數(shù)據(jù)行拢，我們就需要拿著 p2 指針去磁盤中進(jìn)行讀取頁 3。從磁盤中讀取頁 3 后將頁 3 放入內(nèi)存中诞吱，然后進(jìn)行查找舟奠，我們可以找到鍵值 18，然后再拿到頁 3 中的指針 p1房维，定位到頁 8沼瘫。
同樣的頁 8 頁不在內(nèi)存中，我們需要再去磁盤中將頁 8 讀取到內(nèi)存中咙俩。將頁 8 讀取到內(nèi)存中后耿戚。因?yàn)轫撝械臄?shù)據(jù)是鏈表進(jìn)行連接的，而且鍵值是按照順序存放的阿趁，此時(shí)可以根據(jù)二分查找法定位到鍵值 18膜蛔。此時(shí)因?yàn)橐呀?jīng)到數(shù)據(jù)頁了，此時(shí)我們已經(jīng)找到一條滿足條件的數(shù)據(jù)了脖阵，就是鍵值 18 對(duì)應(yīng)的數(shù)據(jù)皂股。因?yàn)槭欠秶檎遥掖藭r(shí)所有的數(shù)據(jù)又都存在葉子節(jié)點(diǎn)命黔，并且是有序排列的呜呐，那么我們就可以對(duì)頁 8 中的鍵值依次進(jìn)行遍歷查找并匹配滿足條件的數(shù)據(jù)。我們可以一直找到鍵值為 22 的數(shù)據(jù)纷铣，然后頁 8 中就沒有數(shù)據(jù)了卵史，此時(shí)我們需要拿著頁 8 中的 p 指針去讀取頁 9 中的數(shù)據(jù)。
因?yàn)轫?9 不在內(nèi)存中搜立，就又會(huì)加載頁 9 到內(nèi)存中以躯，并通過和頁 8 中一樣的方式進(jìn)行數(shù)據(jù)的查找，直到將頁 12 加載到內(nèi)存中啄踊，發(fā)現(xiàn) 41 大于 40忧设，此時(shí)不滿足條件。那么查找到此終止颠通。最終我們找到滿足條件的所有數(shù)據(jù)址晕，總共 12 條記錄：(18,kl), (19,kl), (22,hj), (24,io), (25,vg) , (29,jk), (31,jk) , (33,rt) , (34,ty) , (35,yu) , (37,rt) , (39,rt) 。
利用非聚集索引查找數(shù)據(jù)
非聚集索引中x-y這里顿锰，在葉子節(jié)點(diǎn)中谨垃，不再存儲(chǔ)所有的數(shù)據(jù)了启搂，存儲(chǔ)的是鍵值和主鍵。對(duì)于葉子節(jié)點(diǎn)中的 x-y刘陶，比如 1-1胳赌。左邊的 1 表示的是索引的鍵值，右邊的 1 表示的是主鍵值匙隔。
select * from user where luckNum=33
查找的流程跟聚集索引一樣疑苫，這里就不詳細(xì)介紹了。我們最終會(huì)找到主鍵值 47纷责，找到主鍵后我們需要再到聚集索引中查找具體對(duì)應(yīng)的數(shù)據(jù)信息捍掺，此時(shí)又回到了聚集索引的查找流程≡偕牛看下具體的查找流程圖：
總結(jié)
本篇文章從無數(shù)據(jù)庫(kù)開始講起挺勿，一直引伸出二叉查找樹，詳細(xì)說明了為什么 MySQL 用 B+ 樹作為數(shù)據(jù)的索引饵史，以及在 InnoDB 中數(shù)據(jù)庫(kù)如何通過 B+ 樹索引來存儲(chǔ)數(shù)據(jù)以及查找數(shù)據(jù)满钟。我們一定要記住這句話：數(shù)據(jù)即索引，索引即數(shù)據(jù)胳喷。
原文部分參考地址：http://www.liuzk.com/410.html
