資料庫索引為什麼用B+樹實現？
為什麼大多數資料庫索引都使用B+樹來實現呢？這涉及到資料結構、作業系統、計算機儲存層次結構等等複雜的理論知識，但是不用擔心，這篇文章20分鐘之後就會給你答案。
這篇文章是一系列資料庫索引文章中的最後一篇，這個系列包括了下面四篇文章：
- 資料庫索引是什麼？新華字典來幫你 —— 理解
- 資料庫索引融會貫通 —— 深入
- 20分鐘資料庫索引設計實戰 —— 實戰
- 資料庫索引為什麼用B+樹實現？—— 擴充套件
這一系列涵蓋了資料庫索引從理論到實踐的一系列知識，一站式解決了從理解到融會貫通的全過程，相信每一篇文章都可以給你帶來更深入的體驗。
為什麼使用B+樹？
大家在數學課上一定聽說過一個例子，在一堆已經排好序的數字當中找出一個特定的數字的最好辦法是一種叫“二分查詢”的方式。具體的過程就是先找到這些數字中間的那一個數，然後比較目標數字是大於還是小於這個數；然後根據結果繼續在前一半或者後一半數字中繼續查詢。
這就類似於資料結構中的 二叉樹 ，二叉樹就是如下的一種結構，樹中的每個節點至多可以有兩個子節點，而B+樹每個節點則可以有N個子節點。
這裡就不具體展開講解二叉樹了，我們只需要知道，平衡的二叉樹是 記憶體 中查詢效率最高的一種資料結構就可以了。
但是目前常用的資料庫中，絕大多數的索引都是使用B+樹實現的。那麼為什麼明明是二叉樹查詢效率最高，資料庫中卻偏偏要使用B+樹而不是二叉樹來實現索引呢？
計算機儲存層次結構
計算機中的儲存結構分為好幾個部分，從上到下大致可以分為暫存器、快取記憶體、主儲存器、輔助儲存器。其中主儲存器，也就是我們常說的記憶體；輔助儲存器也被稱為外存，比較常見的就是磁碟、SSD，可以用來儲存檔案。在這個儲存結構中，每一級儲存的速度都比上一級慢很多，所以程式訪問越上層儲存中的資料，速度就會越快。
有過程式設計經驗的小夥伴都知道，程式執行過程中操作的基本都是記憶體，對外存中資料的訪問往往需要寫一些檔案的讀取和寫入程式碼才能實現。這正是因為CPU的計算速度比儲存的I/O速度（輸入/輸出速度）快很多所做的優化，因為CPU在每次計算完成之後就需要等待下一批的資料進入，這個等待的時間越短，計算機執行得越快。
所以對於資料庫索引來說，因為資料量很大，所以基本都是儲存在外存中的，這樣的話資料庫讀取一個索引節點的成本就非常大了。在資料量一樣大的情況下，我們可以知道，B+樹的單個節點中包含的值個數越多那麼樹中需要的節點總數就會越少，這樣查詢一次資料需要訪問的節點數就更少了。
如果你對B+樹還不熟悉，可以到這篇文章中找到答案——資料庫索引融會貫通 。
如果我們把二叉樹看做是特殊的B+樹（每個節點只有一個值和前後兩個指標的B+樹），那麼就可以得出結論： 因為B+樹的節點中包含的值個數（多個值）比二叉樹（1個值）更多，所以在B+樹中查詢所需要的節點數就更少。 那麼如果每次讀取的成本是一樣的話，因為 總成本=讀取次數*單次讀取成本 ，我們就可以證明B+樹的查詢成本就比二叉樹小得多了。
節點讀取成本
但是我們知道，讀取更多資料肯定會需要更大的成本，那麼為什麼資料庫索引使用B+樹還是會比二叉樹更好呢？這就需要一些更高深的作業系統知識來解釋了。
在現代的作業系統中，把資料從外存讀到記憶體所使用的單位一般被稱為“頁”，每次讀取資料都需要讀入整數個的“頁”，而不能讀入半頁或者0.8頁。一頁的大小由作業系統決定，常見的頁大小一般為4KB=4096位元組。所以不管我們是要讀取1位元組還是2KB，最後都是需要讀入一個完整的4KB大小的頁的，那麼一個節點的讀取成本就取決於需要讀入的頁數。
在這樣的情況下，如果一個節點的大小小於一頁的大小，那麼就會有一部分時間花在讀取我們根本不需要的資料上（節點之外的資料），二叉樹在這方面就會浪費很多時間；而如果一個節點的大小大於一頁，哪怕是一頁的整數倍，那我們也可能在一個節點的中間就找到了我們需要的指標進入了下一級的節點，這樣這個指標後面的資料都白白讀取了，如果不需要這些資料可能我們就可以少讀幾頁了。
所以，綜上所述，資料庫索引使用 節點大小恰好等於作業系統一頁大小的B+樹 來實現是效率最高的選擇。