如果用樹(shù)作為索引的數(shù)據(jù)結(jié)構(gòu)，每查找一次數(shù)據(jù)就會(huì)從磁盤中讀取樹(shù)的一個(gè)節(jié)點(diǎn)，也就是一頁(yè)，而二叉樹(shù)的每個(gè)節(jié)點(diǎn)只存儲(chǔ)一條數(shù)據(jù)，并不能填滿一頁(yè)的存儲(chǔ)空間，那多余的存儲(chǔ)空間豈不是要浪費(fèi)了？為了解決二叉平衡搜索樹(shù)的這個(gè)弊端，我們應(yīng)該尋找一種單個(gè)節(jié)點(diǎn)可以存儲(chǔ)更多數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，也就是多路搜索樹(shù)。

1. 多路搜索樹(shù)

1、完全二叉樹(shù)高度：O(log2N)，其中2為對(duì)數(shù)，樹(shù)每層的節(jié)點(diǎn)數(shù)；

2、完全M路搜索樹(shù)的高度：O(logmN)，其中M為對(duì)數(shù)，樹(shù)每層的節(jié)點(diǎn)數(shù)；

3、M路搜索樹(shù)主要用于解決數(shù)據(jù)量大無(wú)法全部加載到內(nèi)存的數(shù)據(jù)存儲(chǔ)。通過(guò)增加每層節(jié)點(diǎn)的個(gè)數(shù)和在每個(gè)節(jié)點(diǎn)存放更多的數(shù)據(jù)來(lái)在一層中存放更多的數(shù)據(jù)，從而降低樹(shù)的高度，在數(shù)據(jù)查找時(shí)減少磁盤訪問(wèn)次數(shù)。

4、所以每層的節(jié)點(diǎn)數(shù)和每個(gè)節(jié)點(diǎn)包含的關(guān)鍵字越多，則樹(shù)的高度越矮。但是在每個(gè)節(jié)點(diǎn)確定數(shù)據(jù)就越慢，但是B樹(shù)關(guān)注的是磁盤性能瓶頸，所以在單個(gè)節(jié)點(diǎn)搜索數(shù)據(jù)的開(kāi)銷可以忽略。

2. B樹(shù)-多路平衡搜索樹(shù)

B樹(shù)是一種M路搜索樹(shù)，B樹(shù)主要用于解決M路搜索樹(shù)的不平衡導(dǎo)致樹(shù)的高度變高，跟二叉樹(shù)退化為鏈表導(dǎo)致性能問(wèn)題一樣。B樹(shù)通過(guò)對(duì)每層的節(jié)點(diǎn)進(jìn)行控制、調(diào)整，如節(jié)點(diǎn)分離，節(jié)點(diǎn)合并，一層滿時(shí)向上分裂父節(jié)點(diǎn)來(lái)增加新的層等操作來(lái)來(lái)保證該M路搜索樹(shù)的平衡。

M為B樹(shù)的階數(shù)或者說(shuō)是路數(shù)，在B樹(shù)中，每個(gè)節(jié)點(diǎn)都是一個(gè)磁盤塊(頁(yè))。每個(gè)非葉子節(jié)點(diǎn)存放了關(guān)鍵字和指向兒子樹(shù)的指針，具體數(shù)量為：M階的B樹(shù)，每個(gè)非葉子節(jié)點(diǎn)存放了M-1個(gè)關(guān)鍵字和M個(gè)指向子樹(shù)的指針。如圖為5階B樹(shù)結(jié)構(gòu)的示意圖：

3. B樹(shù)索引

首先創(chuàng)建一張user表：

create table user(
	id int,
	name varchar,
	primary key(id)
) ROW_FORMAT=COMPACT;

假如我們使用B樹(shù)對(duì)表中的用戶記錄建立索引：

B樹(shù)的每個(gè)節(jié)點(diǎn)占用一個(gè)磁盤塊，磁盤塊也就是頁(yè)，從上圖可以看出，B樹(shù)相對(duì)于平衡二叉樹(shù)，每個(gè)節(jié)點(diǎn)存儲(chǔ)了更多的主鍵key和數(shù)據(jù)data，并且每個(gè)節(jié)點(diǎn)擁有了更多的子節(jié)點(diǎn)，子節(jié)點(diǎn)的個(gè)數(shù)一般稱為階，上述圖中的B樹(shù)為3階B樹(shù)，高度也會(huì)降低。假如我們要查找id=28的用戶信息，那么查找流程如下：

1、根據(jù)根節(jié)點(diǎn)找到頁(yè)1，讀入內(nèi)存。【磁盤I/O操作第1次】

2、比較鍵值28在區(qū)間（17,35），找到頁(yè)1的指針p2；

3、根據(jù)p2指針找到頁(yè)3，讀入內(nèi)存?！敬疟PI/O操作第2次】

4、比較鍵值28在區(qū)間（26,35），找到頁(yè)3的指針p2。

5、根據(jù)p2指針找到頁(yè)8，讀入內(nèi)存?！敬疟PI/O操作第3次】

6、在頁(yè)8中的鍵值列表中找到鍵值28，鍵值對(duì)應(yīng)的用戶信息為(28,po)；

B-Tree相對(duì)于AVLTree縮減了節(jié)點(diǎn)個(gè)數(shù)，使每次磁盤I/O取到內(nèi)存的數(shù)據(jù)都發(fā)揮了作用，從而提高了查詢效率。

4. B+樹(shù)索引

B+Tree是在B-Tree基礎(chǔ)上的一種優(yōu)化，使其更適合實(shí)現(xiàn)外存儲(chǔ)索引結(jié)構(gòu)，B+樹(shù)的性質(zhì)：

1、非葉子節(jié)點(diǎn)的子樹(shù)指針與關(guān)鍵字個(gè)數(shù)相同；

2、為所有葉子節(jié)點(diǎn)增加一個(gè)鏈指針；

3、所有關(guān)鍵字都在葉子節(jié)點(diǎn)出現(xiàn)， 且鏈表中的關(guān)鍵字恰好是有序的；

4、非葉子節(jié)點(diǎn)相當(dāng)于是葉子節(jié)點(diǎn)的索引,葉子節(jié)點(diǎn)相當(dāng)于是存儲(chǔ)(關(guān)鍵字)數(shù)據(jù)的數(shù)據(jù)層；

InnoDB存儲(chǔ)引擎就是用B+Tree實(shí)現(xiàn)其索引結(jié)構(gòu)。

從上一節(jié)中的B-Tree結(jié)構(gòu)圖中可以看到每個(gè)節(jié)點(diǎn)中不僅包含數(shù)據(jù)的key值，還有data值。而每一個(gè)頁(yè)的存儲(chǔ)空間是有限的，如果data數(shù)據(jù)較大時(shí)將會(huì)導(dǎo)致每個(gè)節(jié)點(diǎn)（即一個(gè)頁(yè)）能存儲(chǔ)的key的數(shù)量很小，當(dāng)存儲(chǔ)的數(shù)據(jù)量很大時(shí)同樣會(huì)導(dǎo)致B-Tree的深度較大，增大查詢時(shí)的磁盤I/O次數(shù)，進(jìn)而影響查詢效率。在B+Tree中，所有數(shù)據(jù)記錄節(jié)點(diǎn)都是按照鍵值大小順序存放在同一層的葉子節(jié)點(diǎn)上，而非葉子節(jié)點(diǎn)上只存儲(chǔ)key值信息，這樣可以大大加大每個(gè)節(jié)點(diǎn)存儲(chǔ)的key值數(shù)量，降低B+Tree的高度。

B+Tree相對(duì)于B-Tree有幾點(diǎn)不同：

1、非葉子節(jié)點(diǎn)只存儲(chǔ)鍵值信息和指向子節(jié)點(diǎn)頁(yè)號(hào)的指針；

2、所有葉子節(jié)點(diǎn)之間都有一個(gè)鏈指針；

3、數(shù)據(jù)記錄都存放在葉子節(jié)點(diǎn)中；

根據(jù)上圖我們來(lái)看下 B+ 樹(shù)和 B 樹(shù)有什么不同：

(1) B+ 樹(shù)非葉子節(jié)點(diǎn)上是不存儲(chǔ)數(shù)據(jù)的，僅存儲(chǔ)鍵值，而 B 樹(shù)節(jié)點(diǎn)中不僅存儲(chǔ)鍵值，也會(huì)存儲(chǔ)數(shù)據(jù)。

頁(yè)的大小是固定的，InnoDB 中頁(yè)的默認(rèn)大小是 16KB。如果不存儲(chǔ)數(shù)據(jù)，那么就會(huì)存儲(chǔ)更多的鍵值，相應(yīng)的樹(shù)的階數(shù)就會(huì)更大，樹(shù)就會(huì)更矮更胖，如此一來(lái)我們查找數(shù)據(jù)進(jìn)行磁盤的 IO 次數(shù)又會(huì)再次減少，數(shù)據(jù)查詢的效率也會(huì)更快。

另外，如果我們的 B+ 樹(shù)一個(gè)節(jié)點(diǎn)可以存儲(chǔ) 1000 個(gè)鍵值，那么 3 層 B+ 樹(shù)可以存儲(chǔ) 1000×1000×1000=10 億個(gè)數(shù)據(jù)。一般根節(jié)點(diǎn)是常駐內(nèi)存的(第一次檢索根節(jié)點(diǎn)不用讀取磁盤)，所以一般我們查找 10 億數(shù)據(jù)，只需要 2 次磁盤 IO。

(2) B+ 樹(shù)索引的所有數(shù)據(jù)均存儲(chǔ)在葉子節(jié)點(diǎn)，而且數(shù)據(jù)是按照順序排列的。

B+ 樹(shù)中各個(gè)頁(yè)之間是通過(guò)雙向鏈表連接的，葉子節(jié)點(diǎn)中的數(shù)據(jù)是通過(guò)單向鏈表連接的，通過(guò)這種方式可以找到表中的所有數(shù)據(jù)。B+ 樹(shù)使得范圍查找，排序查找，分組查找以及去重查找變得異常簡(jiǎn)單。而 B 樹(shù)因?yàn)閿?shù)據(jù)分散在各個(gè)節(jié)點(diǎn)，要實(shí)現(xiàn)這一點(diǎn)是很不容易的。

總結(jié)

本篇文章就到這里了，希望能夠給你帶來(lái)幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!  

最新評(píng)論