大數據計數原理1+0=1這你都不會算(四)No.52

這是本坑的第四篇，之前已經說了關於 HashSet 、BitMap 、Bloom Filter 布隆過濾器了，本篇主要講B-樹。要是還不知道前面講了啥的，可以點一下下面的連接看看。

大數據計數原理1+0=1這你都不會算(一)No.47

大數據計數原理1+0=1這你都不會算(二)No.50

大數據計數原理1+0=1這你都不會算(三)No.51

B+樹是現在很多索引系統的數據結構，而B-樹是B+樹的基礎，本次先講B-樹。

而在講B-樹之前，又不得不講二叉搜索樹（BST，Binary Search Tree）。二叉搜索樹只有一個原則，左子樹全部小於根節點，右子樹全部大於根節點。

所以在數據 9、17、28、35、39、65 形成二叉樹的時候，會有下面這兩種截然不同的結構。

而對於磁碟來說，每一次的搜索，就是一次磁碟索引，樹越深，則搜索次數越多，則磁碟IO越多，消耗時間也越多。所以後面又進化出了平衡二叉樹這類控制樹平衡並以此來控制樹的高度的演算法。

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

B-樹的出現就是為了解決二叉樹又深又窄的結構，進而變成又矮又寬的結構。樹越矮代表層次越少，則搜索的次數越少，所以磁碟IO次數越少。B-樹繼承了BST的優良傳統，左子樹 < 根節點 <右子樹，而且每個樹節點都存儲了更多的東西。每個節點不僅僅是只存儲一個數值，而是存儲M-1個數值，以及M個索引，以及額外的索引信息，典型的以空間換時間的數據結構。

一個M階的B-樹的結構定義如下：

1.定義任意非葉子結點最多只有M個兒子；且M>2；

2.根結點的兒子數為[2, M]；

3.除根結點以外的非葉子結點的兒子數為[M/2, M]；

4.每個結點存放至少M/2-1（取上整）和至多M-1個關鍵字；（至少2個關鍵字）

5.非葉子結點的關鍵字個數=指向兒子的指針個數-1；

6.非葉子結點的關鍵字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；

7.非葉子結點的指針：P[1], P[2], …, P[M]；其中P[1]指向關鍵字小於K[1]的

子樹，P[M]指向關鍵字大於K[M-1]的子樹，其它P[i]指向關鍵字屬於(K[i-1], K[i])的子樹；

8.所有葉子結點位於同一層；

經典的3階B-樹結構如下：

一個字都看不懂是嗎？一個一個講給你們聽哈~

經典的3階B-樹。比如以根節點為例，每個節點都有3個子樹。我們可以看到，根節點含有2個（M-1）個數值，這兩個數值分割了三個段P1,P2,P3。若值小於17，則繼續往下P1所指向的子樹搜索。若值大於17而小於35，則往P2所指向子樹搜索。若數值大於35，則往P3所指向子樹搜索。子樹也是相同的操作。

在搜索子樹的過程中，若匹配到值完全相等，則搜索結束，並不需要等到葉子節點才算搜索結束（這個記住，在B+樹里會不一樣）。

因為一個節點和葉子，都存儲了M-1個值（並非1個），而且是多路（並非二叉），所以在樹的結構上，能比二叉搜索樹更加寬，更加矮，這在典型的索引系統中，極大地降低了磁碟的IO次數。因為樹很大，但是搜索的次數又比較少，所以大可以將索引存儲到磁碟中，而不用全部放在內存里。

有小夥伴就要問了，我特么看了這麼久，這跟大數據計數有什麼關係呢？

我們之前都是講，如何將已經出現過的值保存，並索引下來，B-樹就是一個很好的數據結構，來進行值的保存。只要不在樹中出現過的，插入到樹中，並將數值加1，這就可以達到統計的效果了，錯誤率是0。

好了這個系列也到第四篇了，還請小夥伴們多多給意見才是啊，你們的點贊轉發評論支持是我繼續寫的動力。