1. 磁盤基礎(chǔ)知識(shí)

• 分頁(yè)：

現(xiàn)代操作系統(tǒng)都使用虛擬內(nèi)存來印射到物理內(nèi)存履肃，內(nèi)存大小有限且價(jià)格昂貴仔沿，所以數(shù)據(jù)的持久化是在磁盤上。虛擬內(nèi)存榆浓、物理內(nèi)存于未、磁盤都使用頁(yè)作為內(nèi)存讀取的最小單位。一般一頁(yè)為4KB（8個(gè)扇區(qū)，每個(gè)扇區(qū)512B烘浦，8*512B=4KB）抖坪。

• 局部性原理：

1. 當(dāng)一個(gè)數(shù)據(jù)被用到時(shí)，其附近的數(shù)據(jù)也通常會(huì)馬上被使用闷叉。
2. 程序運(yùn)行期間所需要的數(shù)據(jù)通常比較集中擦俐。

• 磁盤預(yù)讀原理：

磁盤讀取依靠的是機(jī)械運(yùn)動(dòng)，分為尋道時(shí)間握侧、旋轉(zhuǎn)延遲蚯瞧、傳輸時(shí)間三個(gè)部分，這三個(gè)部分耗時(shí)相加就是一次磁盤IO的時(shí)間品擎，大概 9ms 左右埋合。這個(gè)成本是訪問內(nèi)存的十萬倍左右；

磁盤讀取的速度遠(yuǎn)小于內(nèi)存萄传，所以盡量減少 I/O 次數(shù)是提高效率的關(guān)鍵甚颂。

根據(jù)局部性原理，且由于磁盤順序讀取的效率很高（不需要尋道時(shí)間秀菱，只需很少的旋轉(zhuǎn)時(shí)間）振诬，所以即使只需要讀取一個(gè)字節(jié)，磁盤也會(huì)讀取一頁(yè)的數(shù)據(jù)衍菱。即磁盤預(yù)讀時(shí)通常會(huì)讀取頁(yè)的整倍數(shù)赶么。

2. 樹基礎(chǔ)知識(shí)回顧

排序二叉樹：左 < 跟 < 右
B 樹：有序數(shù)組 + 多叉平衡樹，節(jié)點(diǎn)存儲(chǔ)關(guān)鍵字脊串、數(shù)據(jù)辫呻、指針；
B+ 樹：有序數(shù)組鏈表 + 多叉平衡樹洪规，非葉子節(jié)點(diǎn)存儲(chǔ)指針印屁、關(guān)鍵字，不存儲(chǔ)數(shù)據(jù)斩例；
紅黑樹：紅黑樹是一種不大嚴(yán)格的平衡樹（平衡樹要求太高）

平衡樹是為了防止二叉查找樹退化為鏈表雄人，而紅黑樹在維持平衡以確保 O(log2(n)) 的同時(shí)，不需要頻繁著調(diào)整樹的結(jié)構(gòu)念赶；

二叉樹的存儲(chǔ)結(jié)構(gòu)

1. 順序存儲(chǔ)（適用于完全二叉樹）

二叉樹順序存儲(chǔ)

index 之間的對(duì)應(yīng)關(guān)系：

完全二叉樹順序存儲(chǔ)

注意：二叉樹的順序存儲(chǔ)只適合存儲(chǔ)完全二叉樹础钠，否則 index 無法和節(jié)點(diǎn)對(duì)應(yīng)起來，會(huì)有點(diǎn)惡心：

非完全二叉樹順序存儲(chǔ)

2. 鏈?zhǔn)酱鎯?chǔ)

二叉樹鏈?zhǔn)酱鎯?chǔ)

這里要好好理解一下叉谜，不然會(huì)影響后面的理解旗吁。

3. 為什么不能使用二叉樹來存儲(chǔ)數(shù)據(jù)庫(kù)索引

先說結(jié)論：

1. 平衡二叉樹進(jìn)行插入/刪除時(shí)，大概率需要通過左旋/右旋來維持平衡停局；
2. 旋轉(zhuǎn)需要加載整個(gè)樹很钓，頻繁旋轉(zhuǎn)效率低香府；
3. 二叉樹的 I/O 次數(shù)近似為 O(log2(n))；
4. 范圍查詢時(shí)码倦，二叉樹的時(shí)間復(fù)雜度會(huì)退化成 O(n)企孩；
5. 二叉樹退化成鏈表時(shí)，時(shí)間復(fù)雜度也近似退化成了 O(n)袁稽；
6. 二叉樹無法使用磁盤預(yù)讀功能勿璃；

其實(shí)單論范圍查詢，在關(guān)系型數(shù)據(jù)庫(kù)中就基本沒有使用二叉樹的可能了推汽。但是為了加深對(duì)知識(shí)的了解补疑，來看看其他的原因。

先剔除掉范圍查詢的情況歹撒，原因 1莲组、2、6 可以通過紅黑樹來解決栈妆，那么其實(shí)就剩下 2 個(gè)原因：

1. I/O 次數(shù)對(duì)比胁编；
2. 磁盤預(yù)讀功能的利用；

4. 二叉樹的 I/O 次數(shù)分析

先說 I/O 次數(shù)：

其實(shí)相比于二叉樹鳞尔，B 樹县匠、B+樹智玻， CPU 的運(yùn)算次數(shù)并沒有變化，甚至增多疗隶。但是 CPU 運(yùn)算次數(shù)相比于 I/O 的消耗而言霞扬，可以忽略不計(jì)糕韧，所以 I/O 次數(shù)是評(píng)價(jià)一個(gè)數(shù)據(jù)庫(kù)索引的效率高低的關(guān)鍵指標(biāo)。

對(duì)于紅黑樹而言喻圃，其 I/O 次數(shù)近似為 log2(n)萤彩，為什么是近似呢？

首先斧拍，索引是存儲(chǔ)在磁盤上的雀扶，磁盤上的數(shù)據(jù)大部分情況下是連續(xù)的，但是隨著增刪改查的發(fā)生肆汹，有可能產(chǎn)生很多碎片愚墓，也就是說：

• 索引在磁盤上的存儲(chǔ)也不一定是連續(xù)的；

這里昂勉，嚴(yán)謹(jǐn)起見浪册，我們來分兩種情況：

1. 索引節(jié)點(diǎn)，即樹的節(jié)點(diǎn)在磁盤上存儲(chǔ)是連續(xù)岗照；

假設(shè)一個(gè)頁(yè)能存儲(chǔ) 5 個(gè)節(jié)點(diǎn)村象，假設(shè)二叉樹如下：

二叉樹

注意笆环，序號(hào)只代表在磁盤中存儲(chǔ)的順序，不代表對(duì)應(yīng)節(jié)點(diǎn)的關(guān)鍵字的值厚者；

二叉樹可能是鏈?zhǔn)酱鎯?chǔ)咧织，也可能是順序存儲(chǔ)。但是這里假設(shè)節(jié)點(diǎn)在磁盤上的存儲(chǔ)是連續(xù)的籍救，所以這里可以近似理解成順序存儲(chǔ)习绢。即使是鏈?zhǔn)酱鎯?chǔ)，無非就是 pNext 指針指向下一個(gè)連續(xù)的內(nèi)存地址而已蝙昙。

現(xiàn)在假設(shè)搜索的結(jié)果是最左邊的葉子節(jié)點(diǎn) 16闪萄，因?yàn)榇疟P預(yù)讀的特性，加上一個(gè)頁(yè)能存儲(chǔ) 5 個(gè)節(jié)點(diǎn)奇颠，第一次 I/O ：

第一次I/O

如上败去，第一次 I/O 就讀取了 5 個(gè)節(jié)點(diǎn)，不僅把根節(jié)點(diǎn)讀取進(jìn)內(nèi)存了烈拒，還把節(jié)點(diǎn) 2 和 4 都讀取進(jìn)去了圆裕，看上去還節(jié)約了兩次 I/O ？好厲害的樣子......

此時(shí)荆几，會(huì)根據(jù)二分法查找吓妆，對(duì)比 1 號(hào)節(jié)點(diǎn)然后去找節(jié)點(diǎn) 2，緊接著找節(jié)點(diǎn) 4吨铸，因?yàn)檫@兩個(gè)節(jié)點(diǎn)都在內(nèi)存中了行拢，所以不需要進(jìn)行 I/O

這里再說一次，序號(hào)不代表節(jié)點(diǎn)的關(guān)鍵字诞吱，而是單純的表示節(jié)點(diǎn)在磁盤中的排列順序舟奠；

緊接著，會(huì)需要 8 號(hào)節(jié)點(diǎn)房维，而 8 不再內(nèi)存中沼瘫，所以進(jìn)行第二次 I/O 同樣是讀取一頁(yè)，即 5 個(gè)節(jié)點(diǎn)：

第二次I/O

這次雖然也是讀取了 5 個(gè)節(jié)點(diǎn)咙俩，但是實(shí)際上只有 8 號(hào)節(jié)點(diǎn)有實(shí)際作用耿戚，其他節(jié)點(diǎn)并沒什么卵用（這是二叉樹無法使用預(yù)讀功能的本質(zhì)），但是現(xiàn)在還沒體現(xiàn)出劣勢(shì)暴浦，現(xiàn)在對(duì)比之后需要 16 號(hào)節(jié)點(diǎn)溅话，繼續(xù)第三次讀取：

第三次I/O

此時(shí)找到了 16歌焦，并將結(jié)果返回飞几。

這是高度為 4 的情況，且只有 31 個(gè)數(shù)據(jù)独撇。但是實(shí)際使用中屑墨，怎么可能就 31 個(gè)數(shù)據(jù)躁锁？假設(shè)要找的是 32 號(hào)節(jié)點(diǎn)，因?yàn)?16 號(hào)節(jié)點(diǎn)之后的 17-20 雖然被加載進(jìn)內(nèi)存了卵史，但是完全沒用战转。那么就需要再進(jìn)行一次 I/O 來加載 32 號(hào)節(jié)點(diǎn)所在的頁(yè)，同時(shí)也會(huì)將 33-36 加載進(jìn)內(nèi)存以躯，但是這些節(jié)點(diǎn)并無卵用槐秧。

如果要找的是 1000 ，10000忧设？

所以刁标，隨著層級(jí)的深入，會(huì)出現(xiàn)：

1. 一個(gè)頁(yè)中只有一個(gè)節(jié)點(diǎn)有用（二分法查找要的是子節(jié)點(diǎn)而不是兄弟節(jié)點(diǎn)）址晕；
2. I/O 次數(shù)近似等于log2(n)膀懈；

即：

1. 第一次 I/O 可能的優(yōu)勢(shì)在層級(jí)加深之后就沒有了；
2. 就算是紅黑樹谨垃，也只能將時(shí)間復(fù)雜度維持在 log2(n)启搂；

上述討論的是索引樹在磁盤上的存儲(chǔ)是連續(xù)的，如果不是連續(xù)的刘陶，那么按頁(yè)讀取到的臟數(shù)據(jù)會(huì)更多胳赌，上述的情況中，前幾次 I/O 讀取到有用的數(shù)據(jù)的概率會(huì)變低易核，所以 I/O 的次數(shù)只會(huì)增多而不會(huì)減少,即仍然是近似于 log2(n)匈织。

5. B/B+樹

B 樹即：多路平衡查找樹；

B 樹的巧妙之處在于：

1. 將一個(gè)節(jié)點(diǎn)的大小設(shè)置為一頁(yè)的大心抵薄；
2. 一個(gè)節(jié)點(diǎn)可以存放多個(gè)關(guān)鍵字（多叉樹）纳决；
3. 自平衡碰逸；

這 3 點(diǎn)結(jié)合起來就可以做到：

1. 一個(gè)節(jié)點(diǎn)大小為一頁(yè)，被加載進(jìn)內(nèi)存時(shí)阔加，這些關(guān)鍵字在進(jìn)行對(duì)比饵史，找出需要 leftChild 還是 rightChild 時(shí)，都是有用的（如最右側(cè)時(shí)需要對(duì)比所有節(jié)點(diǎn)）胜榔；
2. 一個(gè)節(jié)點(diǎn)可以存儲(chǔ)多個(gè)關(guān)鍵字胳喷，有效降低了樹的高度；

B+ 樹的巧妙之處在于：

1. 非葉子節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)夭织，進(jìn)一步增大了一頁(yè)中存儲(chǔ)關(guān)鍵字的數(shù)量吭露；
2. 葉子節(jié)點(diǎn)中存儲(chǔ)數(shù)據(jù)且存在指向下一頁(yè)的鏈表指針，可以使用順序查詢（支持范圍查詢）尊惰；

6. B/B+樹的索引數(shù)量

B 樹的節(jié)點(diǎn)中存儲(chǔ)：指針讲竿、關(guān)鍵字(主鍵)泥兰、數(shù)據(jù)
B+ 樹的非葉子節(jié)點(diǎn)：指針、關(guān)鍵字
B+樹的葉子節(jié)點(diǎn)：指針(鏈表)题禀、關(guān)鍵字鞋诗、數(shù)據(jù)

注意，這里不是絕對(duì)的迈嘹，比如有的 B+ 樹中葉子節(jié)點(diǎn)存儲(chǔ)的不是數(shù)據(jù)削彬，而是指向數(shù)據(jù)的指針。查詢到指針之后再去對(duì)應(yīng)地址取出數(shù)據(jù)秀仲，但是這樣應(yīng)該會(huì)增加一次 I/O 吧融痛，應(yīng)該也是在數(shù)據(jù)量和 I/O 次數(shù)之間做了取舍，具體先不討論啄育。

以 Sqlite3.12 之后為例酌心，page_size = 16k，假設(shè)指針為 8 byte挑豌，假設(shè)關(guān)鍵字類型占 8 byte安券，假設(shè)數(shù)據(jù)占 1 KB；

B 樹的一個(gè)節(jié)點(diǎn)：

b樹

一頁(yè)能存儲(chǔ)的數(shù)據(jù)量為：16kb / (1KB+8byte+8byte) ≈ 16氓英；

高度為 3 的 B 樹能存儲(chǔ) 16 x16 x16 = 4096 條數(shù)據(jù)

相比于二叉樹的 1 個(gè)而言侯勉，確實(shí)有效降低了樹的層級(jí)。而且上述是假設(shè)數(shù)據(jù)為 1KB铝阐，如果數(shù)據(jù)沒那么大址貌，高度為 3 的 B 樹能存儲(chǔ)更多的數(shù)據(jù)，但是如果用在大型數(shù)據(jù)庫(kù)索引上還是不夠徘键。

B+ 樹：

B+樹

如上圖练对，B+樹的核心在于非葉子節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)。

這樣做可以減少非葉子結(jié)點(diǎn)占用的空間吹害，增大一頁(yè)所能存儲(chǔ)的數(shù)據(jù)量螟凭，最大程度減少樹的層級(jí)。

仍然是以上假設(shè)它呀，假如樹的高度為 3 螺男，那么就有兩層存儲(chǔ)關(guān)鍵字+指針，一層葉子節(jié)點(diǎn)來存儲(chǔ)實(shí)際數(shù)據(jù)纵穿。

一頁(yè)能存儲(chǔ)的關(guān)鍵字為：16 * 1024 / (8 + 8) = 1024
一頁(yè)能存儲(chǔ)的數(shù)據(jù)量為：16KB / (1KB + 8byte + 8byte) = 16
（這里計(jì)算不完全準(zhǔn)確下隧，實(shí)際情況應(yīng)該是1頁(yè)數(shù)據(jù)中只有一個(gè)鏈表指針指向下一頁(yè)）
能存儲(chǔ)的關(guān)鍵字為：1024 * 1024 = 1048576；

因?yàn)槎斯?jié)點(diǎn)又有 1024 個(gè)指針谓媒，這些指針可以指向一個(gè)頁(yè)淆院，頁(yè)中存儲(chǔ)數(shù)據(jù)，也就是葉子節(jié)點(diǎn)篙耗，一頁(yè)能存儲(chǔ) 16 個(gè)葉子節(jié)點(diǎn)迫筑，所以總共能索引的數(shù)據(jù)量為 1048576 * 16 ≈ 1600萬宪赶；如果高度為 4 ，則再乘以 1024 約為 17億.....

上述推理中脯燃，理解終端節(jié)點(diǎn)的指針指向一個(gè)頁(yè)搂妻，頁(yè)中存儲(chǔ)著關(guān)鍵字 + 數(shù)據(jù) + 鏈表指針是關(guān)鍵。page 標(biāo)記如下辕棚，有助理解：

理解

雖然葉子節(jié)點(diǎn)很多欲主，一個(gè) page 對(duì)應(yīng)一個(gè)葉子節(jié)點(diǎn)甚至是多個(gè) page 才能存下一個(gè)葉子節(jié)點(diǎn)，但是這些是存在磁盤上的逝嚎，找到對(duì)應(yīng)的 page 之后才去加載對(duì)應(yīng)的 page扁瓢。索引超大數(shù)據(jù)量的同時(shí)，不會(huì)對(duì) I/O 次數(shù)產(chǎn)生影響补君，這就是這個(gè)設(shè)計(jì)的牛逼之處引几。

但是這樣也是有缺點(diǎn)的：

無論查詢結(jié)果如何，都必須走到葉子節(jié)點(diǎn)才結(jié)束挽铁，也就是 I/O 次數(shù)固定為 O(h) 或者說是 log(n)（底數(shù)為節(jié)點(diǎn)子分支個(gè)數(shù)）伟桅，這個(gè) h 一般為 2-3，排除掉根節(jié)點(diǎn)常駐內(nèi)存叽掘，高度為 3 的 B+ 樹進(jìn)行兩次 I/O 就可以索引千萬級(jí)別的數(shù)據(jù),高度為 4 的 B+ 樹楣铁，進(jìn)行 3 次 I/O 就能索引十億級(jí)別的數(shù)據(jù)量，這個(gè)效果還是很好的更扁。

所以盖腕，這個(gè)缺點(diǎn)也可以說成是優(yōu)點(diǎn)：穩(wěn)定（穩(wěn)如一條老狗??）

7. 實(shí)際應(yīng)用

• 紅黑樹優(yōu)點(diǎn)

紅黑樹常用于存儲(chǔ)內(nèi)存中的有序數(shù)據(jù)，增刪很快浓镜，內(nèi)存存儲(chǔ)不涉及 I/O 操作溃列。

• B/B+樹的優(yōu)點(diǎn)

更適合磁盤存儲(chǔ)，減少了樹的層級(jí)膛薛，進(jìn)而減少 I/O 次數(shù)哭廉；

• B 樹和 B+ 樹對(duì)比

都是 B 樹，但是 B+樹更適合范圍查詢相叁，比如 Mysql，且查詢次數(shù)很穩(wěn)定辽幌，為 logn增淹。而 B 樹更適合鍵值對(duì)型的聚合數(shù)據(jù)庫(kù)，比如 MongoDB乌企，查詢次數(shù)最優(yōu)為 O(1)虑润；

紅黑樹更適合內(nèi)存存儲(chǔ)，B 樹更適合鍵值對(duì)存儲(chǔ)加酵，B+ 樹適合范圍查詢拳喻；