先看下B+ Tree資料結構的特點(From Wikipedia).
1. The primary value of a B+ tree is in storing data for efficient retrieval in a block-oriented storage context - in particular, filesystems.
2. B+ trees have very high fanout(number of pointers to child nodes in a node, typically on the order of 100 or more), which reduces the number of I/O operations required to find an element in the tree.
對于第2點, 看看下圖, 每個結點都含有指向下一層的指針, 指針越多, 意味着樹的高度就越矮, 即在塊裝置(常見的就是磁盤)中檢索資料, 需要的I/O次數也就越少.
在MySQL中, 不同的存儲引擎, 使用B+ Tree資料結構, 形成了各自存儲資料的方式. 對于InnoDB存儲引擎來說, 是Clustered index(聚簇索引)的存儲方式, (在Oracle中叫索引組織表, 即index-organized table). 在MyISAM存儲引擎中, 就是堆表的存儲方式. 下圖可以較直覺的反應兩者資料的組織方式.
左上方圖聚簇索引中,
a. 非葉子結點存儲的是, <Primary key, Pointer>.
b. 葉子結點存儲的是, 一行行記錄.
左下方圖二級索引中,
a. 非葉子結點儲存的是, <Key, Pointer>.
b. 葉子結點存儲的是, <Key, Primary key>.
右圖索引結構中,
a. 非葉子結點存儲的是, <Key，Pointer>.
b. 葉子結點存儲的是, <Pointer>, 其指向記錄.
下面看看B+ Tree資料結構的efficient retrieval和high fanout特點, 在InnoDB存儲引擎中是如何展現的. 以左上圖為例, 假設使用Bigint資料類型(8Bytes)作為主鍵, 一條記錄大小為400Bytes, Page大小為16K, 那麼索引樹高度為1, 2, 3層時, 存儲的記錄有多少(注, Pointer大小為6Bytes).
現在普通的SAS盤, 一秒鐘也可以完成200次I/O, 從千萬量級的資料中, 檢索一條記錄, 隻要3次I/O, 即0.015秒就行了, 可見效率之高, 又加之目前一般使用的SSD盤, 最少也要再快50倍.
最後看看兩種資料存儲方式的優缺點.
1. 觀察第二幅圖檔, 在InnoDB存儲引擎中使用二級索引檢索資料時, 由于其葉子結點存儲的是<Key, Primary key>, 在擷取到Primary key時, 還要去檢視聚簇索引, 即回表操作, 才能擷取到記錄. 而在MyISAM存儲引擎中, 主鍵索引和二級索引具有同等地位(隻不過主鍵索引值非空), 檢索資料時, 無需回表. 也許從該點來說MyISAM存儲引擎更适合查詢.
2. 對于DML操作, 一條記錄從400Bytes變更到600, 若不能原地更新的話, 在MyISAM存儲引擎中, 索引葉子結點存儲的是指向記錄的指針, 相比InnoDB存儲引擎來說, 其變動會更大些. 也許從該點來說InnoDB存儲引擎更适合變更. 當然了, 兩者為了預防非原地更新産生的影響, 都會在Page中預留白洞.