大數(shù)據(jù)計數(shù)原理1+0=1這你都不會算(五)
Hello哈，又好久沒聊大數(shù)據(jù)相關(guān)的東西了，是不是又忘記了吖?這次聊聊B-樹的升級版，B+樹。前面的內(nèi)容小伙伴可以回顧一下。
大數(shù)據(jù)計數(shù)原理1+0=1這你都不會算(一)
大數(shù)據(jù)計數(shù)原理1+0=1這你都不會算(二)
大數(shù)據(jù)計數(shù)原理1+0=1這你都不會算(三)
大數(shù)據(jù)計數(shù)原理1+0=1這你都不會算(四)
所謂B+樹，跟B-樹主要有這么幾個差別。
1、只有葉子節(jié)點會保存數(shù)據(jù)，根節(jié)點和子節(jié)點都只把子樹最小的值(或***值)作為索引
2、t階B+樹，除根節(jié)點外，每個子節(jié)點最多可以保有2t個關(guān)鍵字(索引或數(shù)據(jù))
3、葉子節(jié)點除了數(shù)據(jù)外，還有衛(wèi)星數(shù)據(jù)(比如一些屬性啊什么的)
4、每個葉子節(jié)點都有指向下一葉子節(jié)點的指針，方便遍歷和range 搜索。
怎么去找到一個數(shù)據(jù)呢?
從根節(jié)點開始搜索，找到其中一個子樹，然后繼續(xù)遍歷，直到葉子節(jié)點。遍歷葉子節(jié)點的所有數(shù)據(jù)，從而找到對應的數(shù)據(jù)。若需要附屬數(shù)據(jù)，則直接拿衛(wèi)星數(shù)據(jù)。若需要繼續(xù)遍歷這棵樹，則使用next指針進行樹的遍歷。
那現(xiàn)在有哪些成熟的場景在用B+樹呢?
1、數(shù)據(jù)庫索引。
比如Mysql，Oracle等。
2、文件系統(tǒng)索引。
比如NTFS。
3、搜索引擎索引。
比如Lucene以前用B+，現(xiàn)在用FST(Finite State Transducer)了
ElasticSearch是基于Lucene，也就隨著變了。
那為什么這些場景會使用B+樹呢?跟B-樹比起來又有什么差別?
1、搜索更加穩(wěn)定。B+樹的一切搜索都需要付出樹的高度那么多的次數(shù)來進行遍歷，而B-樹可能快也可能慢。
2、數(shù)據(jù)存儲更加密集。B+樹的一切數(shù)據(jù)都存在葉子節(jié)點中，不同與B-樹的數(shù)據(jù)非常分散，所以同一塊硬盤可以比B-樹種存儲的數(shù)據(jù)更加集中連續(xù)，這樣磁盤的手臂就不需要移動太遠。
3、數(shù)據(jù)附屬有了根基。B+樹的葉子節(jié)點有衛(wèi)星數(shù)據(jù)，可以用來存放一些不需要被索引但是需要被查詢出來的數(shù)據(jù)，比如數(shù)據(jù)庫的整一行數(shù)據(jù)。
4、樹的遍歷更加方便。B+樹的葉子節(jié)點中，有指向下一個葉子節(jié)點的指針。與B-樹比較，B-樹在遍歷的時候只能遍歷整棵樹進行多個IO操作，而B+樹只需要順序往下對比即可。因為葉子節(jié)點都是有序的，所以作為范圍查找也比較方便。
那問題來了，這跟大數(shù)據(jù)計數(shù)又有什么關(guān)系呢?
請參照上一篇B-樹，跟B-樹一樣。都是將數(shù)據(jù)存儲起來，然后進行搜索，搜索不到就添加到樹中。
下一篇可能理論性比較強了，知識難度跳躍性比較高，小伙伴們做好準備。
【本文為51CTO專欄作者“大蕉”的原創(chuàng)稿件，轉(zhuǎn)載請通過作者微信公眾號“一名叫大蕉的程序員”獲取授權(quán)】
