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

十載的民權(quán)網(wǎng)站建設(shè)經(jīng)驗(yàn)，針對設(shè)計(jì)、前端、開發(fā)、售后、文案、推廣等六對一服務(wù)，響應(yīng)快，48小時(shí)及時(shí)工作處理。全網(wǎng)營銷推廣的優(yōu)勢是能夠根據(jù)用戶設(shè)備顯示端的尺寸不同，自動調(diào)整民權(quán)建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設(shè)計(jì)，從而大程度地提升瀏覽體驗(yàn)。創(chuàng)新互聯(lián)從事“民權(quán)網(wǎng)站設(shè)計(jì)”,“民權(quán)網(wǎng)站推廣”以來，每個(gè)客戶項(xiàng)目都認(rèn)真落實(shí)執(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點(diǎn), 看看下圖, 每個(gè)結(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層時(shí), 存儲的記錄有多少(注, 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ù)時(shí), 由于其葉子結(jié)點(diǎn)存儲的是<Key, Primary key>, 在獲取到Primary key時(shí), 還要去查看聚簇索引, 即回表操作, 才能獲取到記錄. 而在MyISAM存儲引擎中, 主鍵索引和二級索引具有同等地位(只不過主鍵索引值非空), 檢索數(shù)據(jù)時(shí), 無需回表. 也許從該點(diǎn)來說MyISAM存儲引擎更適合查詢.

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

本文名稱：說說B+Tree
鏈接URL：http://jinyejixie.com/article12/iieogc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供微信公眾號、Google、網(wǎng)站內(nèi)鏈、云服務(wù)器、網(wǎng)站制作、網(wǎng)站收錄

廣告

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