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

創(chuàng)新互聯(lián)致力于互聯(lián)網(wǎng)網(wǎng)站建設與網(wǎng)站營銷，提供做網(wǎng)站、成都網(wǎng)站設計、網(wǎng)站開發(fā)、seo優(yōu)化、網(wǎng)站排名、互聯(lián)網(wǎng)營銷、小程序定制開發(fā)、公眾號商城、等建站開發(fā)，創(chuàng)新互聯(lián)網(wǎng)站建設策劃專家，為不同類型的客戶提供良好的互聯(lián)網(wǎng)應用定制解決方案，幫助客戶在新的全球化互聯(lián)網(wǎng)環(huán)境中保持優(yōu)勢。

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

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

左上方圖聚簇索引中,

a. 非葉子結點存儲的是, .

b. 葉子結點存儲的是, 一行行記錄.

左下方圖二級索引中,

a. 非葉子結點儲存的是, .

b. 葉子結點存儲的是, .

右圖索引結構中,

a. 非葉子結點存儲的是, .

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

下面看看B+ Tree數(shù)據(jù)結構的efficient retrieval和high fanout特點, 在InnoDB存儲引擎中是如何體現(xiàn)的. 以左上圖為例, 假設使用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ù)時, 由于其葉子結點存儲的是, 在獲取到Primary key時, 還要去查看聚簇索引, 即回表操作, 才能獲取到記錄. 而在MyISAM存儲引擎中, 主鍵索引和二級索引具有同等地位(只不過主鍵索引值非空), 檢索數(shù)據(jù)時, 無需回表. 也許從該點來說MyISAM存儲引擎更適合查詢.

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

若感興趣可關注訂閱號”數(shù)據(jù)庫最佳實踐”(DBBestPractice).

另外有需要云服務器可以了解下創(chuàng)新互聯(lián)cdcxhl.cn，海內(nèi)外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。

當前文章：說說B+Tree-創(chuàng)新互聯(lián)
文章源于：http://weahome.cn/article/djsejc.html