大數據計數原理1+0=1這你都不會算(四)
這是本坑的第四篇，之前已經說了關于 HashSet 、BitMap 、Bloom Filter 布隆過濾器了，本篇主要講B-樹。要是還不知道前面講了啥的，可以點一下下面的連接看看。
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。
好了這個系列也到第四篇了，還請小伙伴們多多給意見才是啊，你們的點贊轉發評論支持是我繼續寫的動力。
【本文為51CTO專欄作者“大蕉”的原創稿件，轉載請通過作者微信公眾號“一名叫大蕉的程序員”獲取授權】
