[[205014]]

這是本坑的第四篇，之前已經(jīng)說了關(guān)于 HashSet 、BitMap 、Bloom Filter 布隆過濾器了，本篇主要講B-樹。要是還不知道前面講了啥的，可以點(diǎn)一下下面的連接看看。

大數(shù)據(jù)計(jì)數(shù)原理1+0=1這你都不會算(一)

大數(shù)據(jù)計(jì)數(shù)原理1+0=1這你都不會算(二)

大數(shù)據(jù)計(jì)數(shù)原理1+0=1這你都不會算(三)

B+樹是現(xiàn)在很多索引系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)，而B-樹是B+樹的基礎(chǔ)，本次先講B-樹。

而在講B-樹之前，又不得不講二叉搜索樹(BST，Binary Search Tree)。二叉搜索樹只有一個(gè)原則，左子樹全部小于根節(jié)點(diǎn)，右子樹全部大于根節(jié)點(diǎn)。

所以在數(shù)據(jù) 9、17、28、35、39、65 形成二叉樹的時(shí)候，會有下面這兩種截然不同的結(jié)構(gòu)。

而對于磁盤來說，每一次的搜索，就是一次磁盤索引，樹越深，則搜索次數(shù)越多，則磁盤IO越多，消耗時(shí)間也越多。所以后面又進(jìn)化出了平衡二叉樹這類控制樹平衡并以此來控制樹的高度的算法。

但即便如此，二叉樹在數(shù)據(jù)量比較大的情況下，深度還是太深。

B-樹的出現(xiàn)就是為了解決二叉樹又深又窄的結(jié)構(gòu)，進(jìn)而變成又矮又寬的結(jié)構(gòu)。樹越矮代表層次越少，則搜索的次數(shù)越少，所以磁盤IO次數(shù)越少。B-樹繼承了BST的優(yōu)良傳統(tǒng)，左子樹 < 根節(jié)點(diǎn) <右子樹，而且每個(gè)樹節(jié)點(diǎn)都存儲了更多的東西。每個(gè)節(jié)點(diǎn)不僅僅是只存儲一個(gè)數(shù)值，而是存儲M-1個(gè)數(shù)值，以及M個(gè)索引，以及額外的索引信息，典型的以空間換時(shí)間的數(shù)據(jù)結(jié)構(gòu)。

一個(gè)M階的B-樹的結(jié)構(gòu)定義如下：

1.定義任意非葉子結(jié)點(diǎn)最多只有M個(gè)兒子;且M>2;

2.根結(jié)點(diǎn)的兒子數(shù)為[2, M];

3.除根結(jié)點(diǎn)以外的非葉子結(jié)點(diǎn)的兒子數(shù)為[M/2, M];

4.每個(gè)結(jié)點(diǎn)存放至少M(fèi)/2-1(取上整)和至多M-1個(gè)關(guān)鍵字;(至少2個(gè)關(guān)鍵字)

5.非葉子結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)=指向兒子的指針個(gè)數(shù)-1;

6.非葉子結(jié)點(diǎn)的關(guān)鍵字：K[1], K[2], …, K[M-1];且K[i] < K[i+1];

7.非葉子結(jié)點(diǎn)的指針：P[1], P[2], …, P[M];其中P[1]指向關(guān)鍵字小于K[1]的

子樹，P[M]指向關(guān)鍵字大于K[M-1]的子樹，其它P[i]指向關(guān)鍵字屬于(K[i-1], K[i])的子樹;

8.所有葉子結(jié)點(diǎn)位于同一層;

經(jīng)典的3階B-樹結(jié)構(gòu)如下：

一個(gè)字都看不懂是嗎?一個(gè)一個(gè)講給你們聽哈~

經(jīng)典的3階B-樹。比如以根節(jié)點(diǎn)為例，每個(gè)節(jié)點(diǎn)都有3個(gè)子樹。我們可以看到，根節(jié)點(diǎn)含有2個(gè)(M-1)個(gè)數(shù)值，這兩個(gè)數(shù)值分割了三個(gè)段P1,P2,P3。若值小于17，則繼續(xù)往下P1所指向的子樹搜索。若值大于17而小于35，則往P2所指向子樹搜索。若數(shù)值大于35，則往P3所指向子樹搜索。子樹也是相同的操作。

在搜索子樹的過程中，若匹配到值完全相等，則搜索結(jié)束，并不需要等到葉子節(jié)點(diǎn)才算搜索結(jié)束(這個(gè)記住，在B+樹里會不一樣)。

因?yàn)橐粋€(gè)節(jié)點(diǎn)和葉子，都存儲了M-1個(gè)值(并非1個(gè))，而且是多路(并非二叉)，所以在樹的結(jié)構(gòu)上，能比二叉搜索樹更加寬，更加矮，這在典型的索引系統(tǒng)中，極大地降低了磁盤的IO次數(shù)。因?yàn)闃浜艽螅撬阉鞯拇螖?shù)又比較少，所以大可以將索引存儲到磁盤中，而不用全部放在內(nèi)存里。

有小伙伴就要問了，我特么看了這么久，這跟大數(shù)據(jù)計(jì)數(shù)有什么關(guān)系呢?

我們之前都是講，如何將已經(jīng)出現(xiàn)過的值保存，并索引下來，B-樹就是一個(gè)很好的數(shù)據(jù)結(jié)構(gòu)，來進(jìn)行值的保存。只要不在樹中出現(xiàn)過的，插入到樹中，并將數(shù)值加1，這就可以達(dá)到統(tǒng)計(jì)的效果了，錯(cuò)誤率是0。

好了這個(gè)系列也到第四篇了，還請小伙伴們多多給意見才是啊，你們的點(diǎn)贊轉(zhuǎn)發(fā)評論支持是我繼續(xù)寫的動力。

【本文為51CTO專欄作者“大蕉”的原創(chuàng)稿件，轉(zhuǎn)載請通過作者微信公眾號“一名叫大蕉的程序員”獲取授權(quán)】

戳這里，看該作者更多好文