一、為什么B+樹索引比順序索引文件效率要高
B+樹進化具有的優點
索引節點沒有數據，比較小，能夠完全加載到內存中而且葉子節點之間都是鏈表的結構，所以B+Tree也是可以支持范圍查詢的，而B樹每個節點key和data在一起，則無法區間查找B+樹中因為數據都在葉子節點，每次查詢的時間復雜度是穩定的，因此穩定性保證了B+樹的檢索過程
我們再來看下B+樹的檢索過程
從B+樹的根開始，逐層找到葉子節點。找到葉子節點為對應的數據頁，將數據葉加載到內存中，通過頁目錄的槽采用二分查找的方式先找到一個粗略的記錄分組。在分組中通過鏈表遍歷的方式進行記錄的查找。B+樹頁節點結構
將所有的記錄分成幾個組， 每組會存儲多條記錄，頁目錄存儲的是槽（slot），槽相當于分組記錄的索引，每個槽指針指向了不同組的最后一個記錄我們通過槽定位到組，再查看組中的記錄頁的主要作用是存儲記錄，在頁中記錄以單鏈表的形式進行存儲。
單鏈表優點是插入、刪除方便，缺點是檢索效率不高，最壞的情況要遍歷鏈表所有的節點。因此頁目錄中提供了二分查找的方式，來提高記錄的檢索效率。所以B+樹索引比順序索引文件效率要高。
延伸閱讀：
二、為什么要從AVL樹變成B樹
因為內存的易失性。一般情況下，我們都會選擇將 user 表中的數據和索引存儲在磁盤這種外圍設備中。
但是和內存相比，從磁盤中讀取數據的速度會慢上百倍千倍甚至萬倍，所以，我們應當盡量減少從磁盤中讀取數據的次數。
另外，從磁盤中讀取數據時，都是按照磁盤塊來讀取的，并不是一條一條的讀。
如果我們能把盡量多的數據放進磁盤塊中，那一次磁盤讀取操作就會讀取更多數據，那我們查找數據的時間也會大幅度降低。
如果我們用樹這種數據結構作為索引的數據結構，那我們每查找一次數據就需要從磁盤中讀取一個節點，也就是我們說的一個磁盤塊。
我們都知道平衡二叉樹可是每個節點只存儲一個鍵值和數據的。那說明什么？說明每個磁盤塊僅僅存儲一個鍵值和數據！那如果我們要存儲海量的數據呢？
可以想象到二叉樹的節點將會非常多，高度也會極其高，我們查找數據時也會進行很多次磁盤 IO，我們查找數據的效率將會極低
京公網安備 11010802030320號