大數(shù)據(jù)計數(shù)原理1+0=1這你都不會算(四)
這是本坑的第四篇，之前已經(jīng)說了關(guān)于 HashSet 、BitMap 、Bloom Filter 布隆過濾器了，本篇主要講B-樹。要是還不知道前面講了啥的，可以點一下下面的連接看看。
大數(shù)據(jù)計數(shù)原理1+0=1這你都不會算(一)
大數(shù)據(jù)計數(shù)原理1+0=1這你都不會算(二)
大數(shù)據(jù)計數(shù)原理1+0=1這你都不會算(三)
B+樹是現(xiàn)在很多索引系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)，而B-樹是B+樹的基礎(chǔ)，本次先講B-樹。
而在講B-樹之前，又不得不講二叉搜索樹(BST，Binary Search Tree)。二叉搜索樹只有一個原則，左子樹全部小于根節(jié)點，右子樹全部大于根節(jié)點。
所以在數(shù)據(jù) 9、17、28、35、39、65 形成二叉樹的時候，會有下面這兩種截然不同的結(jié)構(gòu)。
而對于磁盤來說，每一次的搜索，就是一次磁盤索引，樹越深，則搜索次數(shù)越多，則磁盤IO越多，消耗時間也越多。所以后面又進化出了平衡二叉樹這類控制樹平衡并以此來控制樹的高度的算法。
但即便如此，二叉樹在數(shù)據(jù)量比較大的情況下，深度還是太深。
B-樹的出現(xiàn)就是為了解決二叉樹又深又窄的結(jié)構(gòu)，進而變成又矮又寬的結(jié)構(gòu)。樹越矮代表層次越少，則搜索的次數(shù)越少，所以磁盤IO次數(shù)越少。B-樹繼承了BST的優(yōu)良傳統(tǒng)，左子樹 < 根節(jié)點 <右子樹，而且每個樹節(jié)點都存儲了更多的東西。每個節(jié)點不僅僅是只存儲一個數(shù)值，而是存儲M-1個數(shù)值，以及M個索引，以及額外的索引信息，典型的以空間換時間的數(shù)據(jù)結(jié)構(gòu)。
一個M階的B-樹的結(jié)構(gòu)定義如下：
1.定義任意非葉子結(jié)點最多只有M個兒子;且M>2;
2.根結(jié)點的兒子數(shù)為[2, M];
3.除根結(jié)點以外的非葉子結(jié)點的兒子數(shù)為[M/2, M];
4.每個結(jié)點存放至少M/2-1(取上整)和至多M-1個關(guān)鍵字;(至少2個關(guān)鍵字)
5.非葉子結(jié)點的關(guān)鍵字個數(shù)=指向兒子的指針個數(shù)-1;
6.非葉子結(jié)點的關(guān)鍵字：K[1], K[2], …, K[M-1];且K[i] < K[i+1];
7.非葉子結(jié)點的指針：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é)點位于同一層;
經(jīng)典的3階B-樹結(jié)構(gòu)如下：
一個字都看不懂是嗎?一個一個講給你們聽哈~
經(jīng)典的3階B-樹。比如以根節(jié)點為例，每個節(jié)點都有3個子樹。我們可以看到，根節(jié)點含有2個(M-1)個數(shù)值，這兩個數(shù)值分割了三個段P1,P2,P3。若值小于17，則繼續(xù)往下P1所指向的子樹搜索。若值大于17而小于35，則往P2所指向子樹搜索。若數(shù)值大于35，則往P3所指向子樹搜索。子樹也是相同的操作。
在搜索子樹的過程中，若匹配到值完全相等，則搜索結(jié)束，并不需要等到葉子節(jié)點才算搜索結(jié)束(這個記住，在B+樹里會不一樣)。
因為一個節(jié)點和葉子，都存儲了M-1個值(并非1個)，而且是多路(并非二叉)，所以在樹的結(jié)構(gòu)上，能比二叉搜索樹更加寬，更加矮，這在典型的索引系統(tǒng)中，極大地降低了磁盤的IO次數(shù)。因為樹很大，但是搜索的次數(shù)又比較少，所以大可以將索引存儲到磁盤中，而不用全部放在內(nèi)存里。
有小伙伴就要問了，我特么看了這么久，這跟大數(shù)據(jù)計數(shù)有什么關(guān)系呢?
我們之前都是講，如何將已經(jīng)出現(xiàn)過的值保存，并索引下來，B-樹就是一個很好的數(shù)據(jù)結(jié)構(gòu)，來進行值的保存。只要不在樹中出現(xiàn)過的，插入到樹中，并將數(shù)值加1，這就可以達到統(tǒng)計的效果了，錯誤率是0。
好了這個系列也到第四篇了，還請小伙伴們多多給意見才是啊，你們的點贊轉(zhuǎn)發(fā)評論支持是我繼續(xù)寫的動力。
【本文為51CTO專欄作者“大蕉”的原創(chuàng)稿件，轉(zhuǎn)載請通過作者微信公眾號“一名叫大蕉的程序員”獲取授權(quán)】
