?

要了解數(shù)據(jù)庫索引的底層原理砖织，我們就得先了解一種叫樹的數(shù)據(jù)結構，而樹中很經典的一種數(shù)據(jù)結構就是二叉樹庶骄！所以下面我們就從二叉樹到平衡二叉樹碴犬，再到B-樹，最后到B+樹來一步一步了解數(shù)據(jù)庫索引底層的原理按傅！

二叉樹（Binary Search Trees）

??二叉樹是每個結點最多有兩個子樹的樹結構捉超。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用于實現(xiàn)二叉查找樹和二叉堆唯绍。二叉樹有如下特性：

1拼岳、每個結點都包含一個元素以及n個子樹，這里0≤n≤2况芒。

2惜纸、左子樹和右子樹是有順序的，次序不能任意顛倒绝骚。左子樹的值要小于父結點耐版，右子樹的值要大于父結點。

光看概念有點枯燥压汪，假設我們現(xiàn)在有這樣一組數(shù)[35 28 49 13 30 37 60]粪牲，順序的插入到一個數(shù)的結構中，步驟如下

圖1

圖2

圖3

圖4

圖3是錯誤示范蛾魄，請大家在分析二叉樹的時候不要犯這個錯誤虑瀑。

?好了，這就是一棵二叉樹啦滴须！我們能看到，經通過一系列的插入操作之后叽奥，原本無序的一組數(shù)已經變成一個有序的結構了扔水，并且這個樹滿足了上面提到的兩個二叉樹的特性！

但是如果同樣是上面那一組數(shù)朝氓，我們自己升序排列后再插入魔市，會怎么樣呢主届？

??由于是升序插入，新插入的數(shù)據(jù)總是比已存在的結點數(shù)據(jù)都要大待德，所以每次都會往結點的右邊插入君丁，最終導致這棵樹嚴重偏科！＝堋绘闷！上圖就是最壞的情況，也就是一棵樹退化為一個線性鏈表了较坛，這樣查找效率自然就低了印蔗，完全沒有發(fā)揮樹的優(yōu)勢了呢！為了較大發(fā)揮二叉樹的查找效率丑勤，讓二叉樹不再偏科华嘹，保持各科平衡，所以有了平衡二叉樹法竞！

平衡二叉樹 (AVL Trees)

??平衡二叉樹是一種特殊的二叉樹耙厚，所以他也滿足前面說到的二叉樹的兩個特性，同時還有一個特性：

它的左右兩個子樹的高度差的絕對值不超過1岔霸，并且左右兩個子樹都是一棵平衡二叉樹薛躬。

??大家也看到了前面[35 28 49 13 30 37 60]插入完成后的圖，其實就已經是一顆平衡二叉樹啦秉剑。

??那如果按照[35 28 49 13 30 37 60]的順序插入一顆平衡二叉樹泛豪，會怎么樣呢？我們看看插入以及平衡的過程：

整個插入的以及平衡的過程就如上圖所示侦鹏。右子樹與左子樹的高度差絕對值大于1就需要調整诡曙。

??這棵樹始終滿足平衡二叉樹的幾個特性而保持平衡！這樣我們的樹也不會退化為線性鏈表了略水！我們需要查找一個數(shù)的時候就能沿著樹根一直往下找价卤，這樣的查找效率和二分法查找是一樣的呢！

??一顆平衡二叉樹能容納多少的結點呢渊涝？這跟樹的高度是有關系的慎璧，假設樹的高度為h，那每一層最多容納的結點數(shù)量為2^(n-1)跨释，整棵樹最多容納節(jié)點數(shù)為2^0+2^1+2^2+...+2^(h-1)胸私。這樣計算，100w數(shù)據(jù)樹的高度大概在20左右鳖谈，那也就是說從有著100w條數(shù)據(jù)的平衡二叉樹中找一個數(shù)據(jù)岁疼，最壞的情況下需要20次查找。如果是內存操作缆娃，效率也是很高的捷绒！但是我們數(shù)據(jù)庫中的數(shù)據(jù)基本都是放在磁盤中的瑰排，每讀取一個二叉樹的結點就是一次磁盤IO，這樣我們找一條數(shù)據(jù)如果要經過20次磁盤的IO暖侨？那性能就成了一個很大的問題了椭住！那我們是不是可以把這棵樹壓縮一下，讓每一層能夠容納更多的節(jié)點呢字逗？雖然我矮京郑，但是我胖啊...

B-Tree

??這顆矮胖的樹就是B-Tree，注意中間是杠精的杠而不是減扳肛，所以也不要讀成B減Tree了~

??那B-Tree有哪些特性呢傻挂？一棵m階的B-Tree有如下特性：

1、每個結點最多m個子結點挖息。

2金拒、除了根結點和葉子結點外，每個結點最少有m/2（向上取整）個子結點套腹。

3绪抛、如果根結點不是葉子結點，那根結點至少包含兩個子結點电禀。

4幢码、所有的葉子結點都位于同一層。

5尖飞、每個結點都包含k個元素（關鍵字）症副，這里m/2≤k

7、每個元素（關鍵字）字左結點的值政基，都小于或等于該元素（關鍵字）贞铣。右結點的值都大于或等于該元素（關鍵字）。

是不是感覺很懵逼沮明！下面我們以一個[0,1,2,3,4,5,6,7]的數(shù)組插入一顆3階的B-Tree為例辕坝，將所有的條件都串起來，你就明白了荐健！

不管裂變前后酱畅，所有葉子結點都在同一層，滿足第4點特性江场，并且子葉結點的數(shù)量也滿足第2點特性纺酸。

在二叉樹中，每個結點只有一個元素址否。但是在B-Tree中吁峻，每個結點都可能包含多個元素，并且非葉子結點在元素的左右都有指向子結點的指針在张。

?如果需要在B-Tree查找一個元素用含，那流程是怎么樣的呢？我們看下圖帮匾，如果我們要在下面的B-Tree中找到關鍵字24啄骇，那流程如下：

16<24<26所以數(shù)據(jù)在16和26中間找，然后就找到了24

??從這個流程我們能看出瘟斜，B-Tree的查詢效率好像也并不比平衡二叉樹高缸夹。但是查詢所經過的結點數(shù)量要少很多，也就意味著要少很多次的磁盤IO螺句，這對 性能的提升是很大的虽惭。

??前面對B-Tree操作的圖我們能看出來，元素就是類似1蛇尚、2芽唇、3這樣的數(shù)值，但是數(shù)據(jù)庫的數(shù)據(jù)都是一條條的數(shù)據(jù)取劫，如果某個數(shù)據(jù)庫以B-Tree的數(shù)據(jù)結構存儲數(shù)據(jù)匆笤，那數(shù)據(jù)怎么存放的呢？我們看下一張圖

??普通的B-Tree的結點中谱邪，元素就是一個個的數(shù)字炮捧。但是上圖中，我們把元素部分拆分成了key-data的形式惦银，key(數(shù)字)就是數(shù)據(jù)的主鍵咆课，data就是具體的數(shù)據(jù)。這樣我們在找一條數(shù)的時候扯俱，就沿著根結點往下找就ok了书蚪，效率是比較高的。

B+Tree

??B+Tree是在B-Tree基礎上的一種優(yōu)化蘸吓，使其更適合實現(xiàn)外存儲索引結構善炫。B+Tree與B-Tree的結構很像，但是也有幾個自己的特性：

1库继、所有的非葉子節(jié)點只存儲關鍵字信息箩艺。

2、所有衛(wèi)星數(shù)據(jù)（具體數(shù)據(jù)）都存在葉子結點中宪萄。

3艺谆、所有的葉子結點中包含了全部元素的信息。

4拜英、所有葉子節(jié)點之間都有一個鏈指針静汤。

??如果上面B-Tree的圖變成B+Tree，那應該如下：

注意紅色標記框2中的箭頭是雙向的，懶得改了虫给，聲明一下藤抡。請注意一下的該截圖中標記的1、2兩處抹估。

?b+圖1

大家仔細對比于B-Tree的圖能發(fā)現(xiàn)什么不同缠黍？

1、非葉子結點上已經只有key信息了药蜻，滿足上面第1點特性瓷式！

2、所有葉子結點下面都有一個data區(qū)域语泽，滿足上面第2點特性贸典！

3、非葉子結點的數(shù)據(jù)在葉子結點上都能找到踱卵，如根結點的元素4廊驼、8在最底層的葉子結點上也能找到，滿足上面第3點特性颊埃！

4蔬充、注意圖中葉子結點之間的箭頭，滿足滿足上面第4點特性班利！

以上圖為例饥漫，我們來講解一下這顆B+Tree。Mysql的底層規(guī)定一個節(jié)點是16kB,在節(jié)點的每個元素存儲的值是這樣的【索引（比如數(shù)字15）+指向下一個子結點的指針(磁盤文件指針)（15后面的空白）】罗标，在B+Tree中只在葉子節(jié)點存儲數(shù)據(jù)庸队，其他子結點存儲的都是索引以及指針，這樣的話在有限的節(jié)點里面闯割，存儲的索引就大大的增加了彻消，樹的階數(shù)可以變得更小了，在數(shù)據(jù)量在千萬級的情況下宙拉，對數(shù)據(jù)的檢索時間將大大的減少宾尚。下面我們來具體的說明一下。假設上圖中的索引是8位的整型（8B）谢澈，我們的指針占的位置為（4B）,那我們一個元素所占的內存空間就12B煌贴，一個節(jié)點我們可以放多少索引呢？是（(16KB*1024B/KB)/12B=1365）,一個節(jié)點可以存放1365個索引（元素）锥忿。假設我們葉子結點存儲的（data+索引）為1K,那么我們上圖中的3階樹可以存放多少數(shù)據(jù)呢牛郑？我們來計算一下1365*1365*16=29811600，可以存放接近3千萬的數(shù)據(jù)敬鬓，是不是覺得存儲量很大淹朋，效率很高笙各。同樣的索引來查找，用B+tree和B-Tree有啥差別础芍？我們來看一下杈抢，B-Tree的前面講過了不講了。現(xiàn)在我們根據(jù)索引來查找30者甲，同樣的從根結點開始春感，15<30<56在根節(jié)點的左子樹上,20<30<49在這之間，繼續(xù)往下找虏缸，然后你就找到了30 下的一條條數(shù)據(jù)。注意嫩实，在查找的時候我們是不是都進行了比較刽辙，B+Tree只是比較索引，但是B-Tree是帶著數(shù)據(jù)的索引進行比較甲献，速度誰更快不用講宰缤。

在看B+Tree的時候“b+圖1”中的紅色標記1，大家都注意到了20的data在20的右子樹的葉子結點上晃洒，這個稱之為冗余結點慨灭，為什么要這么設計呢，這就引出另外一個問題球及，那就是圖中的紅色標記2氧骤，雙向箭頭。其實葉子結點 除了存儲指針還存儲了前后葉子結點的鏈針吃引，這個鏈針和冗余結點的好處就是方便我們的范圍查找筹陵，同時檢索效率也大大的提高了。

B-Tree or B+Tree镊尺？

在講這兩種數(shù)據(jù)結構在數(shù)據(jù)庫中的選擇之前朦佩，我們還需要了解的一個知識點是操作系統(tǒng)從磁盤讀取數(shù)據(jù)到內存是以磁盤塊（block）為基本單位的，位于同一個磁盤塊中的數(shù)據(jù)會被一次性讀取出來庐氮，而不是需要什么取什么语稠。即使只需要一個字節(jié)，磁盤也會從這個位置開始弄砍，順序向后讀取一定長度的數(shù)據(jù)放入內存仙畦。這樣做的理論依據(jù)是計算機科學中著名的局部性原理：當一個數(shù)據(jù)被用到時，其附近的數(shù)據(jù)也通常會馬上被使用输枯。

預讀的長度一般為頁（page）的整倍數(shù)议泵。頁是計算機管理存儲器的邏輯塊，硬件及操作系統(tǒng)往往將主存和磁盤存儲區(qū)分割為連續(xù)的大小相等的塊桃熄，每個存儲塊稱為一頁（在許多操作系統(tǒng)中先口，頁得大小通常為4k）型奥。

B-Tree和B+Tree該如何選擇呢？都有哪些優(yōu)劣呢碉京？

1厢汹、B-Tree因為非葉子結點也保存具體數(shù)據(jù)，所以在查找某個關鍵字的時候找到即可返回谐宙。而B+Tree所有的數(shù)據(jù)都在葉子結點烫葬，每次查找都得到葉子結點。所以在同樣高度的B-Tree和B+Tree中凡蜻，B-Tree查找某個關鍵字的效率更高搭综。

2、由于B+Tree所有的數(shù)據(jù)都在葉子結點划栓，并且結點之間有指針連接兑巾，在找大于某個關鍵字或者小于某個關鍵字的數(shù)據(jù)的時候刊苍，B+Tree只需要找到該關鍵字然后沿著鏈表遍歷就可以了坠宴，而B-Tree還需要遍歷該關鍵字結點的根結點去搜索。

3汰蓉、由于B-Tree的每個結點（這里的結點可以理解為一個數(shù)據(jù)頁）都存儲主鍵+實際數(shù)據(jù)委煤，而B+Tree非葉子結點只存儲關鍵字信息堂油，而每個頁的大小有限是有限的，所以同一頁能存儲的B-Tree的數(shù)據(jù)會比B+Tree存儲的更少碧绞。這樣同樣總量的數(shù)據(jù)府框，B-Tree的深度會更大，增大查詢時的磁盤I/O次數(shù)头遭，進而影響查詢效率寓免。

鑒于以上的比較，所以在常用的關系型數(shù)據(jù)庫中计维，都是選擇B+Tree的數(shù)據(jù)結構來存儲數(shù)據(jù)袜香！下面我們以mysql的innodb存儲引擎為例講解，其他類似sqlserver鲫惶、oracle的原理類似蜈首！

延伸拓展：

Hash數(shù)據(jù)結構存儲

? 在mysql中建立索引的時候，可以選擇是用hash,還是B+Tree.Hash是這樣的欠母，當你存入索引的時候會通過hash算法生成一個hashCode欢策，在存入內存的時候就將你的這個hashCode和地址指針配對存入。這樣做的好處就是當你在查詢的時候赏淌，能夠快速的定位踩寇，根本不需要去比較查找，只要根據(jù)這個值通過hash算法就可以找到你要的數(shù)據(jù)了六水。但是這種結構在實際應用中基本上是很少用的（至少我是沒遇到過）俺孙，為什么呢辣卒？因為在實際的應用中我們的sql語句查詢用的比較多的是范圍查找而不是精準定位。

綜上所述睛榄，B+Tree成為了mysql,oracle等數(shù)據(jù)庫的底層數(shù)據(jù)結構的不二之選荣茫。

索引的底層數(shù)據(jù)結構和算法

聚集索引&非聚集索引

? 知道數(shù)據(jù)庫基本的數(shù)據(jù)結構以后啡莉，下面我們來了解索引的底層數(shù)據(jù)結構和算法，用mySql為例。

MySql?有兩種索引引擎：MyISAM索引實現(xiàn)（非聚集），innodb索引實現(xiàn)（聚集索引）；存儲引擎是形容數(shù)據(jù)的表的朝聋。

MyISAM索引實現(xiàn)（非聚集）

? ?這種索引下面會有三個文檔嗡午，分別是：

MyISAM存儲引擎是形容數(shù)據(jù)的表的:

xxx_MyISAM.frm :存儲表定義結構

xxx_MyISAM.myd ：存儲表數(shù)據(jù)

xxx_MyISAM.myi ：存儲表的索引

從以上三個文件結合B+Tree的知識，大家就會很清楚的知道冀痕，MyISAM索引將表結構荔睹、索引、數(shù)據(jù)是分開在三個文件中進行存儲的言蛇。

以下圖為例，我們來進行講解：

從上圖中紅色方框標記可以看到MyISAM的葉子結點中除了索引以外腊尚，存儲的的不是data而是地址指針婿斥，在找數(shù)據(jù)的時候是通過地址指針去尋找的數(shù)據(jù)。除此之外索引的也是分開存儲的（紅色圓形標記）民宿，所以說MyISAM是非聚集的活鹰。

非聚集索引的存儲結構與前面是一樣的，不同的是在葉子結點的數(shù)據(jù)部分存的不再是具體的數(shù)據(jù)，而數(shù)據(jù)的聚集索引的key。所以通過非聚集索引查找的過程是先找到該索引key對應的聚集索引的key孵班，然后再拿聚集索引的key到主鍵索引樹上查找對應的數(shù)據(jù)，這個過程稱為回表扇售！

innodb引擎數(shù)據(jù)存儲（聚集）

Innodb引擎下面有以下兩種文件：

xxx.frm:?存儲表定義結構

xxx.ibd:存儲表數(shù)據(jù)和表的索引

它的聚集結構我們來看一下下圖：

圖innoDB-1

從上圖中我們可以看到InnoDB的存儲跟那兩個文件是保持一致的，它的葉子結點存儲的就是索引+完整的數(shù)據(jù)食零。

如圖圖innoDB-1所示困乒，如果我們插入一個28，那么這個數(shù)應該插入在20與30之間贰谣，這樣的話相應的（20,30）前后指針就需要變化娜搂，如果我們再插入一個29的話我們的B+TREE就需要分裂迁霎，一旦分裂的話，整顆樹就要重構百宇，因為指針地址變更考廉。數(shù)據(jù)量大的時候樹的重構是非常耗時的，所以innodb要求主鍵自增携御！

在InnoDB存儲引擎中昌粤，也有頁的概念，默認每個頁的大小為16K啄刹，也就是每次讀取數(shù)據(jù)時都是讀取4*4k的大袖套！假設我們現(xiàn)在有一個用戶表誓军，我們往里面寫數(shù)據(jù)袱讹。這里需要注意的一點是，在某個頁內插入新行時昵时，為了不減少數(shù)據(jù)的移動捷雕，通常是插入到當前行的后面或者是已刪除行留下來的空間，所以在某一個頁內的數(shù)據(jù)并不是完全有序的壹甥，但是為了數(shù)據(jù)訪問順序性非区，在每個記錄中都有一個指向下一條記錄的指針，以此構成了一條單向有序鏈表盹廷。

? 這棵樹的非葉子結點上存的都是主鍵，那如果一個表沒有主鍵會怎么樣久橙？在innodb中俄占，如果一個表沒有主鍵，那默認會找建了唯一索引的列淆衷，如果也沒有缸榄，則會生成一個隱形的字段作為主鍵！

有數(shù)據(jù)插入那就有刪除祝拯，如果這個用戶表頻繁的插入和刪除甚带，那會導致數(shù)據(jù)頁產生碎片，頁的空間利用率低佳头，還會導致樹變的“虛高”鹰贵，降低查詢效率！這可以通過索引重建來消除碎片提高查詢效率康嘉！

主鍵自增寫入時新插入的數(shù)據(jù)不會影響到原有頁碉输，插入效率高！且頁的利用率高亭珍！但是如果主鍵是無序的或者隨機的敷钾，那每次的插入可能會導致原有頁頻繁的分裂枝哄，影響插入效率！降低頁的利用率阻荒！這也是為什么在innodb中建議設置主鍵自增的原因挠锥！

innodb引擎數(shù)據(jù)查找

??數(shù)據(jù)插入了怎么查找呢？

1侨赡、找到數(shù)據(jù)所在的頁蓖租。這個查找過程就跟前面說到的B+Tree的搜索過程是一樣的，從根結點開始查找一直到葉子結點辆毡。

2菜秦、在頁內找具體的數(shù)據(jù)。讀取第1步找到的葉子結點數(shù)據(jù)到內存中舶掖，然后通過分塊查找的方法找到具體的數(shù)據(jù)球昨。

?這跟我們在新華字典中找某個漢字是一樣的，先通過字典的索引定位到該漢字拼音所在的頁眨攘，然后到指定的頁找到具體的漢字主慰。innodb中定位到頁后用了哪種策略快速查找某個主鍵呢？這我們就需要從頁結構開始了解鲫售。

??左邊藍色區(qū)域稱為Page Directory共螺，這塊區(qū)域由多個slot組成，是一個稀疏索引結構情竹，即一個槽中可能屬于多個記錄藐不，最少屬于4條記錄，最多屬于8條記錄秦效。槽內的數(shù)據(jù)是有序存放的雏蛮，所以當我們尋找一條數(shù)據(jù)的時候可以先在槽中通過二分法查找到一個大致的位置。

??右邊區(qū)域為數(shù)據(jù)區(qū)域阱州，每一個數(shù)據(jù)頁中都包含多條行數(shù)據(jù)挑秉。注意看圖中最上面和最下面的兩條特殊的行記錄Infimum和Supremum，這是兩個虛擬的行記錄苔货。在沒有其他用戶數(shù)據(jù)的時候Infimum的下一條記錄的指針指向Supremum犀概，當有用戶數(shù)據(jù)的時候，Infimum的下一條記錄的指針指向當前頁中最小的用戶記錄夜惭，當前頁中最大的用戶記錄的下一條記錄的指針指向Supremum，至此整個頁內的所有行記錄形成一個單向鏈表滥嘴。

??行記錄被Page Directory邏輯的分成了多個塊木蹬，塊與塊之間是有序的，也就是說“4”這個槽指向的數(shù)據(jù)塊內最大的行記錄的主鍵都要比“8”這個槽指向的數(shù)據(jù)塊內最小的行記錄的主鍵要小。但是塊內部的行記錄不一定有序镊叁。

??每個行記錄的都有一個nowned的區(qū)域（圖中粉紅色區(qū)域）尘颓，nowned標識這個這個塊有多少條數(shù)據(jù)，偽記錄Infimum的nowned值總是1晦譬，記錄Supremum的nowned的取值范圍為[1,8]疤苹，其他用戶記錄nowned的取值范圍[4,8]，并且只有每個塊中最大的那條記錄的nowned才會有值敛腌，其他的用戶記錄的n_owned為0卧土。

所以當我們要找主鍵為6的記錄時，先通過二分法在稀疏索引中找到對應的槽像樊，也就是Page Directory中“8”這個槽尤莺，“8”這個槽指向的是該數(shù)據(jù)塊中最大的記錄，而數(shù)據(jù)是單向鏈表結構所以無法逆向查找生棍，所以需要找到上一個槽即“4”這個槽颤霎，然后通過“4”這個槽中最大的用戶記錄的指針沿著鏈表順序查找到目標記錄。

InnoDB的數(shù)據(jù)引擎同時要求主鍵盡量是整型涂滴，為什么友酱？我們下面來分析一下

? 假設我們的主鍵是英文字符串，那么innodb數(shù)據(jù)引擎在進行b+Tree的構建的時候就會將英文字母翻譯成數(shù)字柔纵，比如as缔杉，（假如：a=65，s=83）那么innodb會將其翻譯成6583,6583就是主鍵搁料，中間的一次翻譯就會導致效率的降低或详。所以InnoDB數(shù)據(jù)引擎要求主鍵盡量是整型。

? 當存在多個索引的時候具體的聚集結構是什么樣的呢郭计，如下圖所示：

當你又多個索引的時候就將你的索引排序就可以了鸭叙。

innodb與MyISAM兩種存儲引擎對比

??那MyISAM與innodb在存儲上有啥不同呢，根據(jù)以上的圖我們能看到的不同是

1拣宏、MyISAM主鍵索引樹的葉子結點的數(shù)據(jù)區(qū)域沒有存放實際的數(shù)據(jù)，存放的是數(shù)據(jù)記錄的地址杠人。

2勋乾、MyISAM數(shù)據(jù)的存儲不是按主鍵順序存放的，按寫入的順序存放嗡善。

也就是說innodb引擎數(shù)據(jù)在物理上是按主鍵順序存放辑莫，而MyISAM引擎數(shù)據(jù)在物理上按插入的順序存放。并且MyISAM的葉子結點不存放數(shù)據(jù)罩引，所以非聚集索引的存儲結構與聚集索引類似各吨，在使用非聚集索引查找數(shù)據(jù)的時候通過非聚集索引樹就能直接找到數(shù)據(jù)的地址了，不需要回表袁铐，這比innodb的搜索效率會更高呢揭蜒！

以上是個人的理解横浑，僅供參考，望與各位碼農共勉屉更，不喜勿噴徙融，謝謝。