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