為什么大多數(shù)數(shù)據(jù)庫索引都使用B+樹來實現(xiàn)呢艇肴？這涉及到數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)叁温、計算機存儲層次結(jié)構(gòu)等等復(fù)雜的理論知識再悼，但是不用擔(dān)心，這篇文章20分鐘之后就會給你答案膝但。
這篇文章是一系列數(shù)據(jù)庫索引文章中的最后一篇冲九，這個系列包括了下面四篇文章：
數(shù)據(jù)庫索引融會貫通 —— 深入
20分鐘數(shù)據(jù)庫索引設(shè)計實戰(zhàn) —— 實戰(zhàn)
這一系列涵蓋了數(shù)據(jù)庫索引從理論到實踐的一系列知識莺奸，一站式解決了從理解到融會貫通的全過程丑孩，相信每一篇文章都可以給你帶來更深入的體驗。
為什么使用B+樹灭贷？
大家在數(shù)學(xué)課上一定聽說過一個例子温学，在一堆已經(jīng)排好序的數(shù)字當(dāng)中找出一個特定的數(shù)字的最好辦法是一種叫“二分查找”的方式。具體的過程就是先找到這些數(shù)字中間的那一個數(shù)甚疟，然后比較目標(biāo)數(shù)字是大于還是小于這個數(shù)仗岖；然后根據(jù)結(jié)果繼續(xù)在前一半或者后一半數(shù)字中繼續(xù)查找。
這就類似于數(shù)據(jù)結(jié)構(gòu)中的二叉樹览妖，二叉樹就是如下的一種結(jié)構(gòu)轧拄，樹中的每個節(jié)點至多可以有兩個子節(jié)點，而B+樹每個節(jié)點則可以有N個子節(jié)點讽膏。
這里就不具體展開講解二叉樹了檩电，我們只需要知道，平衡的二叉樹是內(nèi)存中查詢效率最高的一種數(shù)據(jù)結(jié)構(gòu)就可以了府树。
但是目前常用的數(shù)據(jù)庫中俐末，絕大多數(shù)的索引都是使用B+樹實現(xiàn)的。那么為什么明明是二叉樹查詢效率最高奄侠，數(shù)據(jù)庫中卻偏偏要使用B+樹而不是二叉樹來實現(xiàn)索引呢鹅搪？
計算機存儲層次結(jié)構(gòu)
計算機中的存儲結(jié)構(gòu)分為好幾個部分，從上到下大致可以分為寄存器遭铺、高速緩存、主存儲器恢准、輔助存儲器魂挂。其中主存儲器，也就是我們常說的內(nèi)存馁筐；輔助存儲器也被稱為外存涂召，比較常見的就是磁盤、SSD敏沉，可以用來保存文件果正。在這個存儲結(jié)構(gòu)中，每一級存儲的速度都比上一級慢很多盟迟，所以程序訪問越上層存儲中的數(shù)據(jù)秋泳，速度就會越快。
有過編程經(jīng)驗的小伙伴都知道攒菠，程序運行過程中操作的基本都是內(nèi)存迫皱，對外存中數(shù)據(jù)的訪問往往需要寫一些文件的讀取和寫入代碼才能實現(xiàn)。這正是因為CPU的計算速度比存儲的I/O速度（輸入/輸出速度）快很多所做的優(yōu)化辖众，因為CPU在每次計算完成之后就需要等待下一批的數(shù)據(jù)進(jìn)入卓起，這個等待的時間越短和敬，計算機運行得越快。
所以對于數(shù)據(jù)庫索引來說戏阅，因為數(shù)據(jù)量很大昼弟，所以基本都是保存在外存中的，這樣的話數(shù)據(jù)庫讀取一個索引節(jié)點的成本就非常大了奕筐。在數(shù)據(jù)量一樣大的情況下舱痘，我們可以知道，B+樹的單個節(jié)點中包含的值個數(shù)越多那么樹中需要的節(jié)點總數(shù)就會越少救欧，這樣查詢一次數(shù)據(jù)需要訪問的節(jié)點數(shù)就更少了衰粹。
如果你對B+樹還不熟悉，可以到這篇文章中找到答案——數(shù)據(jù)庫索引融會貫通 笆怠。
如果我們把二叉樹看做是特殊的B+樹（每個節(jié)點只有一個值和前后兩個指針的B+樹）铝耻，那么就可以得出結(jié)論：因為B+樹的節(jié)點中包含的值個數(shù)（多個值）比二叉樹（1個值）更多，所以在B+樹中查詢所需要的節(jié)點數(shù)就更少蹬刷。那么如果每次讀取的成本是一樣的話瓢捉，因為總成本=讀取次數(shù)*單次讀取成本，我們就可以證明B+樹的查詢成本就比二叉樹小得多了办成。
節(jié)點讀取成本
但是我們知道泡态，讀取更多數(shù)據(jù)肯定會需要更大的成本，那么為什么數(shù)據(jù)庫索引使用B+樹還是會比二叉樹更好呢迂卢？這就需要一些更高深的操作系統(tǒng)知識來解釋了某弦。
在現(xiàn)代的操作系統(tǒng)中，把數(shù)據(jù)從外存讀到內(nèi)存所使用的單位一般被稱為“頁”而克，每次讀取數(shù)據(jù)都需要讀入整數(shù)個的“頁”靶壮，而不能讀入半頁或者0.8頁。一頁的大小由操作系統(tǒng)決定员萍，常見的頁大小一般為4KB=4096字節(jié)腾降。所以不管我們是要讀取1字節(jié)還是2KB，最后都是需要讀入一個完整的4KB大小的頁的碎绎，那么一個節(jié)點的讀取成本就取決于需要讀入的頁數(shù)螃壤。
在這樣的情況下，如果一個節(jié)點的大小小于一頁的大小筋帖，那么就會有一部分時間花在讀取我們根本不需要的數(shù)據(jù)上（節(jié)點之外的數(shù)據(jù)）奸晴，二叉樹在這方面就會浪費很多時間；而如果一個節(jié)點的大小大于一頁日麸，哪怕是一頁的整數(shù)倍蚁滋，那我們也可能在一個節(jié)點的中間就找到了我們需要的指針進(jìn)入了下一級的節(jié)點，這樣這個指針后面的數(shù)據(jù)都白白讀取了，如果不需要這些數(shù)據(jù)可能我們就可以少讀幾頁了辕录。
所以睦霎，綜上所述，數(shù)據(jù)庫索引使用節(jié)點大小恰好等于操作系統(tǒng)一頁大小的B+樹來實現(xiàn)是效率最高的選擇走诞。
