先看下B+ Tree數(shù)據(jù)結(jié)構(gòu)的特點(From Wikipedia).

十載的民權(quán)網(wǎng)站建設(shè)經(jīng)驗，針對設(shè)計、前端、開發(fā)、售后、文案、推廣等六對一服務(wù)，響應(yīng)快，48小時及時工作處理。全網(wǎng)營銷推廣的優(yōu)勢是能夠根據(jù)用戶設(shè)備顯示端的尺寸不同，自動調(diào)整民權(quán)建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設(shè)計，從而大程度地提升瀏覽體驗。創(chuàng)新互聯(lián)從事“民權(quán)網(wǎng)站設(shè)計”,“民權(quán)網(wǎng)站推廣”以來，每個客戶項目都認(rèn)真落實執(zhí)行。

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點, 看看下圖, 每個結(jié)點都含有指向下一層的指針, 指針越多, 意味著樹的高度就越矮, 即在塊設(shè)備(常見的就是磁盤)中檢索數(shù)據(jù), 需要的I/O次數(shù)也就越少.

在MySQL中, 不同的存儲引擎, 使用B+ Tree數(shù)據(jù)結(jié)構(gòu), 形成了各自存儲數(shù)據(jù)的方式. 對于InnoDB存儲引擎來說, 是Clustered index(聚簇索引)的存儲方式, (在Oracle中叫索引組織表, 即index-organized table). 在MyISAM存儲引擎中, 就是堆表的存儲方式. 下圖可以較直觀的反應(yīng)兩者數(shù)據(jù)的組織方式.

左上方圖聚簇索引中,

a. 非葉子結(jié)點存儲的是, .

b. 葉子結(jié)點存儲的是, 一行行記錄.

左下方圖二級索引中,

a. 非葉子結(jié)點儲存的是, .

b. 葉子結(jié)點存儲的是, .

右圖索引結(jié)構(gòu)中,

a. 非葉子結(jié)點存儲的是, .

b. 葉子結(jié)點存儲的是, , 其指向記錄.

下面看看B+ Tree數(shù)據(jù)結(jié)構(gòu)的efficient retrieval和high fanout特點, 在InnoDB存儲引擎中是如何體現(xiàn)的. 以左上圖為例, 假設(shè)使用Bigint數(shù)據(jù)類型(8Bytes)作為主鍵, 一條記錄大小為400Bytes, Page大小為16K, 那么索引樹高度為1, 2, 3層時, 存儲的記錄有多少(注, Pointer大小為6Bytes).

現(xiàn)在普通的SAS盤, 一秒鐘也可以完成200次I/O, 從千萬量級的數(shù)據(jù)中, 檢索一條記錄, 只要3次I/O, 即0.015秒就行了, 可見效率之高, 又加之目前一般使用的SSD盤, 最少也要再快50倍.

最后看看兩種數(shù)據(jù)存儲方式的優(yōu)缺點.

1. 觀察第二幅圖片, 在InnoDB存儲引擎中使用二級索引檢索數(shù)據(jù)時, 由于其葉子結(jié)點存儲的是, 在獲取到Primary key時, 還要去查看聚簇索引, 即回表操作, 才能獲取到記錄. 而在MyISAM存儲引擎中, 主鍵索引和二級索引具有同等地位(只不過主鍵索引值非空), 檢索數(shù)據(jù)時, 無需回表. 也許從該點來說MyISAM存儲引擎更適合查詢.

2. 對于DML操作, 一條記錄從400Bytes變更到600, 若不能原地更新的話, 在MyISAM存儲引擎中, 索引葉子結(jié)點存儲的是指向記錄的指針, 相比InnoDB存儲引擎來說, 其變動會更大些. 也許從該點來說InnoDB存儲引擎更適合變更. 當(dāng)然了, 兩者為了預(yù)防非原地更新產(chǎn)生的影響, 都會在Page中預(yù)留空洞.