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

Hello哈，又好久沒聊大數據相關的東西了，是不是又忘記了吖？這次聊聊B-樹的升級版，B+樹。前面的內容小夥伴可以回顧一下。

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

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

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

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

所謂B+樹，跟B-樹主要有這麼幾個差別。

1、只有葉子節點會保存數據，根節點和子節點都只把子樹最小的值（或最大值）作為索引

2、t階B+樹，除根節點外，每個子節點最多可以保有2t個關鍵字（索引或數據）

3、葉子節點除了數據外，還有衛星數據（比如一些屬性啊什麼的）

4、每個葉子節點都有指向下一葉子節點的指針，方便遍歷和range 搜索。

怎麼去找到一個數據呢？

從根節點開始搜索，找到其中一個子樹，然後繼續遍歷，直到葉子節點。遍歷葉子節點的所有數據，從而找到對應的數據。若需要附屬數據，則直接拿衛星數據。若需要繼續遍歷這棵樹，則使用next指針進行樹的遍歷。

那現在有哪些成熟的場景在用B+樹呢？

1、資料庫索引。

比如Mysql，Oracle等。

2、文件系統索引。

比如NTFS。

3、搜索引擎索引。

比如Lucene以前用B+，現在用FST（Finite State Transducer）了

ElasticSearch是基於Lucene，也就隨著變了。

那為什麼這些場景會使用B+樹呢？跟B-樹比起來又有什麼差別？

1、搜索更加穩定。B+樹的一切搜索都需要付出樹的高度那麼多的次數來進行遍歷，而B-樹可能快也可能慢。

2、數據存儲更加密集。B+樹的一切數據都存在葉子節點中，不同與B-樹的數據非常分散，所以同一塊硬碟可以比B-樹種存儲的數據更加集中連續，這樣磁碟的手臂就不需要移動太遠。

3、數據附屬有了根基。B+樹的葉子節點有衛星數據，可以用來存放一些不需要被索引但是需要被查詢出來的數據，比如資料庫的整一行數據。

4、樹的遍歷更加方便。B+樹的葉子節點中，有指向下一個葉子節點的指針。與B-樹比較，B-樹在遍歷的時候只能遍歷整棵樹進行多個IO操作，而B+樹只需要順序往下對比即可。因為葉子節點都是有序的，所以作為範圍查找也比較方便。

那問題來了，這跟大數據計數又有什麼關係呢？

請參照上一篇B-樹，跟B-樹一樣。都是將數據存儲起來，然後進行搜索，搜索不到就添加到樹中。

下一篇可能理論性比較強了，知識難度跳躍性比較高，小夥伴們做好準備。

分享轉發點贊留言一下嘛。又不會多塊肚腩，你說是吧？