1.介紹

B樹是一種自平衡的搜索樹數(shù)據(jù)結構，常用于數(shù)據(jù)庫和文件系統(tǒng)中的索引結構。它具有以下好處和功能：

1. 高效的查找操作：B樹的特點是每個節(jié)點可以存儲多個關鍵字，并且保持有序。通過在節(jié)點上進行二分查找，可以快速定位目標關鍵字的位置，從而實現(xiàn)高效的查找操作。

2. 平衡性：B樹通過自平衡的方式維護樹的平衡性，即保證樹的每個葉子節(jié)點到根節(jié)點的路徑長度相等。這種平衡性能夠確保各種操作的時間復雜度保持在較低水平，例如插入、刪除和查找等操作都可以在對數(shù)時間內完成。

3. 適應大型數(shù)據(jù)集：B樹適用于存儲大型數(shù)據(jù)集，并且可以處理非常大的索引。其節(jié)點可以存儲多個關鍵字，因此在相同層數(shù)的情況下，B樹可以存儲更多的數(shù)據(jù)。

4. 支持范圍查詢：由于B樹的節(jié)點有序，因此可以很方便地進行范圍查詢。通過定位范圍的起始和結束關鍵字所在的節(jié)點，可以快速地獲取指定范圍內的數(shù)據(jù)。

5. 高效的插入和刪除操作：B樹通過平衡性的維護，使得插入和刪除操作具有較低的時間復雜度。它可以通過調整節(jié)點的結構，避免過深或過淺的樹結構，從而保持樹的平衡。

總的來說，B樹是一種高效的數(shù)據(jù)結構，能夠應對大規(guī)模數(shù)據(jù)集的索引需求，并提供快速的查找、插入和刪除操作。它在數(shù)據(jù)庫和文件系統(tǒng)中廣泛應用，為數(shù)據(jù)的組織和訪問提供了便利。

2.代碼分析

1.分裂

當鍵的數(shù)量超過 2t - 1的時候就會進行分裂操作,規(guī)則就是中間的向上分裂，大的交給一個新的節(jié)點，小的交給自己

如果不是葉子節(jié)點就需要把后半部分子節(jié)點給新的節(jié)點，

2.添加

1. 首先，根據(jù)給定的關鍵字，從根節(jié)點開始向下搜索，找到合適的葉子節(jié)點。

2. 在葉子節(jié)點中插入新的關鍵字。如果葉子節(jié)點未滿，直接插入；否則，執(zhí)行步驟3。

3. 當葉子節(jié)點已滿時，需要進行分裂操作。將當前節(jié)點一分為二，得到兩個新的葉子節(jié)點，并選擇一個關鍵字提升到父節(jié)點中。

4. 如果父節(jié)點也已滿，則重復步驟3，層層遞歸地向上分裂，直到找到一個非滿節(jié)點或達到樹的頂部。

5. 完成插入操作后，需要更新祖先節(jié)點的關鍵字信息。如果某個節(jié)點發(fā)生了分裂，它提升的關鍵字需要插入到其父節(jié)點中，并根據(jù)大小順序進行調整。

通過以上步驟，B樹的插入操作可以保持樹的平衡性。在插入過程中，B樹會根據(jù)節(jié)點的容量進行自動調整，使得樹的高度保持相對較低，從而確保各種操作的效率。

需要注意的是，在插入操作中可能會出現(xiàn)關鍵字重復的情況。對于B樹來說，可以允許存在相同的關鍵字，而在查找操作時，會按照節(jié)點中關鍵字的大小順序進行搜索。因此，在插入過程中需要根據(jù)具體需求來處理關鍵字重復的情況。

3.查找

1. 從根節(jié)點開始，比較要查找的關鍵字與當前節(jié)點中的關鍵字。

2. 如果找到了匹配的關鍵字，則表示查找成功，結束操作。

3. 如果要查找的關鍵字小于當前節(jié)點的最小關鍵字，則進入當前節(jié)點的左子樹進行繼續(xù)查找。

4. 如果要查找的關鍵字大于當前節(jié)點的最大關鍵字，則進入當前節(jié)點的右子樹進行繼續(xù)查找。

5. 重復步驟 3 和 4，直到找到匹配的關鍵字或者到達葉子節(jié)點。

6. 如果到達葉子節(jié)點仍然沒有找到匹配的關鍵字，則表示查找失敗，結束操作。

在B樹的查找過程中，關鍵字的比較會指導搜索方向，通過不斷地按照關鍵字的大小順序向下搜索，可以快速地找到目標關鍵字或者判斷其不存在。

需要注意的是，B樹中允許存在相同的關鍵字，因此在查找操作中，如果存在多個相同的關鍵字，可以根據(jù)具體需求選擇返回其中一個或全部。此外，B樹的查找操作具有較好的平均時間復雜度，可以在較短的時間內完成查詢。

3.代碼實現(xiàn)

1.準備工作

//節(jié)點類
class BTreeNode {// B樹的階數(shù)int t;List<Integer> keys;//關鍵字List<BTreeNode> childNodes;//孩子boolean leaf;//判斷節(jié)點是否是葉子結點public BTreeNode(int t, boolean leaf) {this.t = t;this.leaf = leaf;this.keys = new ArrayList<>();this.childNodes = new ArrayList<>();}
}

2.升序遍歷樹

 public void traverse() {int i;for (i = 0; i < keys.size(); i++) {if (!leaf) {//去索引為i的孩子里面繼續(xù)找childNodes.get(i).traverse();}System.out.print(keys.get(i) + " ");}//最后還剩一個關鍵字的孩子節(jié)點if (!leaf) {childNodes.get(i).traverse();}}

3.查找值所在的位置

 public int search(int key) {int i = 0;//先找到比值小和等的節(jié)點 然后小的遞歸找孩子while (i < keys.size() && key > keys.get(i)) {i++;}//等的if (i < keys.size() && key == keys.get(i)) {return i;} else if (leaf) {//都到葉子了還沒找到就無了return -1;} else {//遞歸繼續(xù)去他的子節(jié)點找  小的return childNodes.get(i).search(key);}}

4.添加

 public void insertNonFull(int key) {//處理節(jié)點未滿的情況int i = keys.size() - 1;if (leaf) {//葉節(jié)點while (i >= 0 && key < keys.get(i)) {//從后往前 找出比你小的那個ii--;}keys.add(i + 1, key);//因為第i個位置是比你小的,所以你要插入后面一個} else {//非葉節(jié)點while (i >= 0 && key < keys.get(i)) {//找到要插入子節(jié)點的位置i--;}//判斷子節(jié)點是否需要分裂操作if (childNodes.get(i + 1).keys.size() == (2 * t) - 1) {splitChild(i + 1, childNodes.get(i + 1));if (key > keys.get(i + 1)) {i++;}}//分裂完畢 或者 不需要分裂 遞歸插入childNodes.get(i + 1).insertNonFull(key);}}

5.分裂

 public void splitChild(int i, BTreeNode y) {//處理節(jié)點滿的情況進行分裂操作BTreeNode z = new BTreeNode(y.t, y.leaf);keys.add(i, y.keys.get(t - 1));//中間的上移childNodes.add(i + 1, z);//創(chuàng)建新的孩子for (int j = 0; j < t - 1; j++) {//后面的移動到新的里面z.keys.add(j, y.keys.get(j + t));}if (!y.leaf) {//后半部分子節(jié)點移動到新的節(jié)點for (int j = 0; j < t; j++) {z.childNodes.add(j, y.childNodes.get(j + t));}}//主要總用時為了情況沒有用的部分//獲取被拆分節(jié)點后半部分的關鍵字和子節(jié)點部分。y.keys.subList(t - 1, y.keys.size()).clear();//方法用于刪除列表中的元素(獲取完刪除)y.childNodes.subList(t, y.childNodes.size()).clear();}
}

6.遍歷查詢

class BTree {BTreeNode root;//根節(jié)點int t;//樹中的最小度數(shù)//指定默認樹的度數(shù)是2public BTree() {this(2);}public BTree(int t) {this.root = null;this.t = t;}//遍歷樹public void traverse() {//樹不為空就可以遍歷if (root != null) {root.traverse();}}//查找節(jié)點的位置public int search(int key) {if (root != null) {return root.search(key);}return -1;}//插入節(jié)點public void insert(int key) {if (root == null) {root = new BTreeNode(t, true);root.keys.add(0, key);} else {if (root.keys.size() == (2 * t) - 1) {BTreeNode s = new BTreeNode(t, false);s.childNodes.add(0, root);s.splitChild(0, root);int i = 0;if (s.keys.get(0) < key) {i++;}s.childNodes.get(i).insertNonFull(key);root = s;} else {root.insertNonFull(key);}}}
}