B樹的節(jié)點(diǎn)包括：Key鍵值，Index索引值，Data數(shù)據(jù)
B樹維基百科參考
B樹別稱：多路查找平衡樹，多分支的平衡的查找樹（多叉的平衡的搜索樹）
維基百科對B樹的定義為“在計算機(jī)科學(xué)中，B樹（B-tree）是一種樹狀數(shù)據(jù)結(jié)構(gòu)，它能夠存儲數(shù)據(jù)、對其進(jìn)行排序并允許以O(shè)(log n)的時間復(fù)雜度運(yùn)行進(jìn)行查找、順序讀取、插入和刪除的數(shù)據(jù)結(jié)構(gòu)。B樹，概括來說是一個節(jié)點(diǎn)可以擁有多于2個子節(jié)點(diǎn)的二叉查找樹。與自平衡二叉查找樹不同，B-樹為系統(tǒng)最優(yōu)化大塊數(shù)據(jù)的讀和寫操作。B-tree算法減少定位記錄時所經(jīng)歷的中間過程，從而加快存取速度。普遍運(yùn)用在數(shù)據(jù)庫和文件系統(tǒng)?！?/p>
B樹結(jié)構(gòu)定義
- 可以看作是對2-3查找樹的一種擴(kuò)展，即他允許每個節(jié)點(diǎn)有M-1個子節(jié)點(diǎn)。
- 根節(jié)點(diǎn)至少有兩個子節(jié)點(diǎn)
- 每個節(jié)點(diǎn)有M-1個key，并且以升序排列
- 位于M-1和M key的子節(jié)點(diǎn)的值位于M-1 和M key對應(yīng)的Value之間
- 其它節(jié)點(diǎn)至少有M/2個子節(jié)點(diǎn)
下圖是一個M=4 階的B樹:
4階B樹參考
可以看到B樹是2-3樹的一種擴(kuò)展，他允許一個節(jié)點(diǎn)有多于2個的元素。
B樹的插入及平衡化操作和2-3樹很相似，這里就不介紹了。下面是往B樹中依次插入6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4的演示動畫：
B數(shù)據(jù)構(gòu)建參考
