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

創(chuàng)新互聯(lián)致力于互聯(lián)網(wǎng)網(wǎng)站建設(shè)與網(wǎng)站營銷，提供做網(wǎng)站、成都網(wǎng)站設(shè)計(jì)、網(wǎng)站開發(fā)、seo優(yōu)化、網(wǎng)站排名、互聯(lián)網(wǎng)營銷、小程序定制開發(fā)、公眾號商城、等建站開發(fā)，創(chuàng)新互聯(lián)網(wǎng)站建設(shè)策劃專家，為不同類型的客戶提供良好的互聯(lián)網(wǎng)應(yī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點(diǎn), 看看下圖, 每個結(jié)點(diǎn)都含有指向下一層的指針, 指針越多, 意味著樹的高度就越矮, 即在塊設(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é)點(diǎn)存儲的是, <Primary key, Pointer>.

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

左下方圖二級索引中,

a. 非葉子結(jié)點(diǎn)儲存的是, <Key, Pointer>.

b. 葉子結(jié)點(diǎn)存儲的是, <Key, Primary key>.

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

a. 非葉子結(jié)點(diǎn)存儲的是, <Key，Pointer>.

b. 葉子結(jié)點(diǎn)存儲的是, <Pointer>, 其指向記錄.

下面看看B+ Tree數(shù)據(jù)結(jié)構(gòu)的efficient retrieval和high fanout特點(diǎn), 在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)缺點(diǎn).

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

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

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

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

本文名稱：說說B+Tree-創(chuàng)新互聯(lián)
當(dāng)前路徑：http://jinyejixie.com/article22/djsejc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供全網(wǎng)營銷推廣、網(wǎng)站營銷、動態(tài)網(wǎng)站、做網(wǎng)站、外貿(mào)建站、網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)