8分鐘,複習一遍B樹,B+樹!

語言: CN / TW / HK

theme: smartblue

簡單介紹

什麼是B樹,B+樹?

B 樹

B 樹(B- 樹) 指的是 Balance Tree,又名平衡多路(即不止兩個子樹)查詢樹,並且所有葉子節點位於同一層。

B+ 樹

B+ 樹基於B 樹和葉子節點順序訪問指標進行實現,具有 B 樹的平衡性,並且通過順序訪問指標來提高區間查詢的效能。通常用於資料庫和作業系統的檔案系統中。

B+ 樹的特點是能夠保持資料穩定有序,其插入與修改擁有較穩定的對數時間複雜度。B+ 樹元素自底向上插入,這與二叉樹恰好相反。

B樹,B+樹的使用場景

檔案系統和資料庫系統中常用的B/B+ 樹,他通過對每個節點儲存個數的擴充套件,使得對連續的資料能夠進行較快的定位和訪問,能夠有效減少查詢時間,提高儲存的空間區域性性從而減少IO操作。他廣泛用於檔案系統及資料庫中,如:

  • WindowsHPFS 檔案系統
  • MacHFSHFS+ 檔案系統
  • LinuxResiserFSXFSExt3FSJFS 檔案系統
  • 資料庫:ORACLEMYSQLSQLSERVER 等中
  • 資料庫:ORACLEMYSQLSQLSERVER 等中

具體一點

  • B樹

    • MongoDB資料庫使用,單次查詢平均快於MySQL (但側面來看MySQL至少平均查詢耗時差不多)
    • ORACLE資料庫
  • B+樹

    • MySQL資料庫普遍使用B+樹來實現索引結構

      • MyISAM索引實現
      • InnoDB索引實現

這裡注意了,Redis 用的是 skiplist(跳錶) 作為底層,而沒有使用平衡樹這一結構

磁碟概述

現在我們知道了B,B+樹主要用在檔案系統和資料庫了。本篇我們將簡單的介紹磁碟這個儲存結構,為接下來的學習做鋪墊。

磁碟結構示意圖

  • 整體結構

    image.png

  • 橫切面

    image.png

我們都知道,計算機的儲存管理是分層的,各層次之間的速度差距比較大,尤其是輔存(磁碟)和主存之間的速度。我們也知道磁碟訪問比較慢,為什麼會慢呢?

  • 關於訪存

    CPU訪問磁碟時,磁碟主要乾了這些事:

    1. 尋道:磁頭擺一擺,找到對應的柱面
    2. 定位:盤面轉一轉,磁頭定位到指定扇區

在訪存的兩個步驟中,因為是機械操作比不上主存的電訊號傳播,所以自然就慢了不少,磁碟訪問慢了,訪問效率自然就跟不上了。

那麼能不能再不改變這種機械運動的情況下提升訪存效率呢?

能。使用索引就可以。

  • 什麼是索引?

    索引就好比是書的目錄,比如當我們檢視一本字典的時候,目錄就相當於我們的對照表。索引一般以檔案形式儲存在磁碟上,索引檢索需要磁碟I/O操作。

所以這就要求我們建立一個好的索引來幫助我們提升訪存效率。

磁碟讀寫原理

  • 區域性性原理

    在一小段時間裡,程式執行所訪問的儲存空間侷限於某個記憶體區域。(在這一小段時間內程式只會用這一部分記憶體的這一小撮資料)

  • 磁碟預讀

    在有了區域性性原理之後。這程式執行依次要一個數據,現在我們知道它要的資料基本都是一堆一堆的湊在一起的,那我就可以在它要之前我這個磁碟先讀著我這個扇區下面的內容,不管程式是否需要。這個就是磁碟預讀,預讀的長度一般為頁(page)的整數倍。(頁是資料儲存的單位。頁面從主儲存器載入到處理器中。頁由單元塊或塊組組成。)

在瞭解了磁碟以後,我們知道問題是如何利用索引來提高訪存速度。而B,B+樹就是為了解決這個問題而存在的。

為什麼使用B,B+樹?

傳統用來搜尋的平衡二叉樹有很多,如 AVL 樹,紅黑樹等。這些樹在一般情況下查詢效能非常好,但當資料非常大的時候它們就無能為力了。(這些樹的高度比較高)

原因當資料量非常大時,記憶體不夠用,大部分資料只能存放在磁碟上,只有需要的資料才載入到記憶體中。一般而言記憶體訪問的時間約為 50 ns,而磁碟在 10 ms 左右。速度相差了近 5 個數量級,磁碟讀取時間遠遠超過了資料在記憶體中比較的時間。這說明程式大部分時間會阻塞在磁碟 IO 上。

那麼我們如何提高程式效能?減少磁碟 IO 次數,像 AVL 樹,紅黑樹這類平衡二叉樹從設計上無法“迎合”磁碟。

平衡二叉樹是通過旋轉來保持平衡的,而旋轉是對整棵樹的操作,若部分載入到記憶體中則無法完成旋轉操作。 其次平衡二叉樹的高度相對較大為 log n(底數為2),這樣邏輯上很近的節點實際可能非常遠,無法很好的利用磁碟預讀(區域性性原理)

在最壞的情況下,一次IO就只能獲得一個結點的值,所以在最壞的情況下,不管是紅黑樹還是AVL樹、B樹、B+樹,他們對應的磁碟操作是樹的高度。而B樹和B+樹的高度是低的,適應資料庫和檔案系統的。

所以 AVL 樹,紅黑樹這類平衡二叉樹在資料庫和檔案系統上的選擇就被 pass 了。

更多細節將在 “剖析 B樹,B+樹” 章節解釋

B樹,B+樹的特徵

本篇為對B樹和B+樹的特徵列舉, 詳細的部分在下一章對比中給出

B 樹的特徵

  • 一個m階的B樹有如下幾個特徵:

    • 若根結點不是終端結點,則至少有2棵子樹。
    • 每個中間節點都包含k-1個元素和k個孩子,其中 m/2 <= k <= m
    • 每一個葉子節點都包含k-1個元素,其中 m/2 <= k <= m
    • 所有的葉子結點都位於同一層。
    • 每個節點中的元素從小到大排列,節點當中k-1個元素正好是k個孩子包含的元素的值域分劃。
  • B 樹(3階)示例:

    image.png

    B+ 樹的特徵

  • 一棵m階B+樹具有如下幾個特徵:

    • 有k個子樹的中間節點包含有k個元素(B樹中是k-1個元素),每個元素不儲存資料,只用來索引,所有資料都儲存在葉子節點。
    • 所有的葉子結點中包含了全部元素的資訊,及指向含這些元素記錄的指標,且葉子結點本身依關鍵字的大小自小而大順序連結。
    • 所有的中間節點元素都同時存在於子節點,在子節點元素中是最大(或最小)元素。
  • B+ 樹(3階)示例:

    image-20220921152142893

    解釋:

    B+ 樹始終要保持最大元素在根節點當中。

    B+ 樹的葉子節點包含了全量元素資訊。並且每一個葉子節點都帶有指向下一個節點的指標,形成了一個有序連結串列

無論是B樹還是B+樹,最底層呈現的都是有序序列。

AVL樹 vs B樹 vs B+樹

關於平衡二叉樹的內容可以看我的另一篇部落格:https://juejin.cn/post/7136389871266070564

AVL 樹(左),B 樹(右)

image.png - B樹的節點和AVL樹的節點結構不同

平衡二叉樹的節點,每個最多有一個數據和最多兩個子樹。

B樹的節點,每個節點可以有不止一個數據,同時可以擁有的子樹數量是階數決定的。
  • B樹的查詢效率更高

    B樹的每個節點可以表示的資訊更多,因此整個樹更加“矮胖”,這在從磁碟中查詢資料(先讀取到記憶體、後查詢)的過程中,可以減少磁碟 IO 的次數,從而提升查詢速度。

B樹既然這麼多好處了,那麼B+樹呢?

B 樹(上),B+樹(下)

image.png

  • B+樹的磁碟讀寫代價更低(節點結構不同決定)

    B+樹的非葉子節點不儲存資料,所以其內部結點相對B樹更小,如果把所有同一非葉子結點的關鍵字存放在同一盤塊中,那麼盤塊所能容納的關鍵字數量也越多。相對來說IO讀寫次數也就降低了,查詢速度更快了。

  • B+樹查詢效率更穩定

    B+樹內非葉子節點不儲存資料,而是隻是葉子結點關鍵字的索引,所有 data 儲存在葉節點導致查詢時間複雜度固定為 log n。而B樹查詢時間複雜度不固定,與 key 在樹中的位置有關,最好為O(1)。 所以B+樹中任何關鍵字的查詢必須走一條從根結點到葉子結點的路,所有關鍵字查詢的路徑長度相同,導致每一個數據的查詢效率相當,而對於B樹來說,因為每個結點都存有具體的資料,因此其查詢速度不穩定,可能很快也可能很慢。

    舉個例子:

    我們查詢 9 這個元素,從上圖可以看出,key 為 9 的節點就在第一層,B樹只需要一次磁碟 IO 即可完成查詢。所以說B樹的查詢最好時間複雜度是 O(1)。由於B+樹所有的 data 域都在根節點,所以查詢 key 為 9的節點必須從根節點索引到葉節點,時間複雜度固定為 O(log n)。

  • B+樹便於範圍查詢

    B樹在提高了IO效能的同時,並沒有解決元素遍歷效率低下的問題。為了解決這個問題,B+樹應運而生。

    B+樹只需要遍歷葉子結點就可以實現整棵樹的遍歷(B+樹葉子結點維護有序連結串列。在資料庫中基於範圍的查詢也是非常頻繁的,因此MySQLInnodb引擎就使用了B+樹作為其索引的資料結構

深入剖析 B樹,B+樹

衛星資料

什麼是衛星資料?

衛星資料指索引元素所指向的資料記錄

比如資料庫中的某一行。

在B樹中,無論非葉子結點還是葉子結點都帶有衛星資料;

image-20220922134010842

而在B+樹中只有葉子結點帶有衛星資料,其餘非終端結點僅僅是索引,沒有任何資料關聯。

image.png

拿MySQL中的聚簇索引和非聚簇索引舉例

在MySQL資料庫的聚簇索引中,葉子結點直接包含衛星資料;在非聚簇索引中,葉子結點帶有指向衛星資料的指標。

B 樹

23樹,234樹

在我的文章:8分鐘,複習一遍紅黑樹!中,我介紹了紅黑樹的前身——234樹,而實際上234樹就是4階B樹,23樹就是3階B樹

這樣一來,本章的目的之一 “對B樹的剖析” 就不是難事了。

  • 234樹(4階B樹):是一種多叉樹,它的每個節點最多有3個數據項和4個子節點。
  • 23樹(3階B樹):是一種多叉樹,它的每個節點最多有2個數據項和3個子節點。

所以,B樹的插入以及刪除等操作完全就可以用234樹,23樹來解釋。

下一個篇章我們將介紹B樹的常見操作。

B 樹的操作

插入

關於234樹的插入操作在8分鐘,複習一遍紅黑樹!中已經詳細說明,這裡就不展開了。

查詢

image.png 假設每個節點有 n 個 key值,被分割為 n+1 個區間,注意,B樹的 key 和 data 實際是聚合在一起的,因為B樹的所有節點都是衛星資料

一般而言,根節點都在記憶體中,B樹以每個節點為一次磁碟 IO。

比如上圖中,若搜尋 key 為 3 節點的 data,首先在根節點進行二分查詢(因為 keys 有序,二分最快),判斷 key 3 小於 key 5,所以定位到最左側的節點,此時進行一次磁碟 IO,將該節點從磁碟讀入記憶體,接著繼續進行上述過程,直到找到該 key 為止。

查詢虛擬碼:

Node* BTreeSearch(Root *root, Key key)  {      Node* node;  ​      if(root == NULL)          return NULL;      node = BinarySearch(root,key); // 在根節點進行二分查詢,進行當前節點定位      if(node->key == key)     {// 找到key了          return node;     }else{          root = ReadDisk(node->next); // 進行一次磁碟IO,將下一個節點讀入到記憶體          BTreeSearch(root, key); // 遞迴尋找     }  }

B 樹如何迎合磁碟

本篇我們從“迎合”磁碟的角度來看看B樹的設計。

索引的效率依賴於磁碟 IO 的次數,快速索引需要有效的減少磁碟 IO 次數

索引的原理?B樹是如何快速索引的?

索引的原理其實是不斷的縮小查詢範圍,就如我們平時用字典查單詞一樣,先找首字母縮小範圍,再第二個字母等等。

平衡二叉樹是每次將範圍分割為兩個區間。為了更快,B樹每次將範圍分割為多個區間,區間越多,定位資料越快越精確。那麼如果節點為區間範圍,每個節點就較大了

實際設計中,我們把一個節點設為一個頁,直接申請頁大小的空間。(磁碟儲存單位是按 block 分的,一般為 512 Byte。磁碟 IO 一次讀取若干個 block,我們稱為一頁,具體大小和作業系統有關,一般為 4 k,8 k或 16 k)

計算機記憶體分配是按頁對齊的,這樣就實現了一個節點只需要一次 IO。

image.png

上圖是一棵簡化的B樹,多叉的好處非常明顯,有效的降低了B樹的高度。現在的高度為底數很大的 log n,底數大小與節點的子節點數目有關,一般一棵B樹的高度在 3 層左右。

層數低,每個節點區確定的範圍更精確,範圍縮小的速度越快(比二叉樹深層次的搜尋肯定快很多)。

上面說了一個節點需要進行一次 IO,那麼總 IO 的次數就縮減為了 log n 次。

B樹的每個節點是 n 個有序的序列(a_1,a_2,a_3…a_n),並將該節點的子節點分割成 n+1 個區間來進行索引(X_1< a_1, a_2 < X_2 < a_3, … , a_{n+1} < X_n < a_n, X_{n+1} > a_n)。

解釋:B樹的每個節點,都是存多個值的,不像二叉樹那樣,一個節點就一個值,B樹把每個節點都給了一點的範圍區間,區間更多的情況下,搜尋也就更快了,比如:有1-100個數,二叉樹一次只能分兩個範圍,0-50和51-100,而B樹,分成4個範圍 1-25, 25-50,51-75,76-100 一次就能篩選走四分之三的資料。所以作為多叉樹的B樹是更快的

所以,B樹就是一個很好的索引結構,因為它有效的減少了磁碟 IO 次數!

B 樹程式碼實現

本篇程式碼引用自:

https://github.com/tclxspy/Articles/blob/master/algorithm/MD/%E7%AE%97%E6%B3%95%2316--B%E6%A0%91%E5%AE%8C%E6%95%B4%E4%BB%A3%E7%A0%81Java%E5%AE%9E%E7%8E%B0.md

java  public class BTree<Key extends Comparable<Key>, Value>  {      // max children per B-tree node = M-1      // (must be even and greater than 2)      private static final int M = 4;  ​      private Node root;       // root of the B-tree      private int height;      // height of the B-tree      private int n;           // number of key-value pairs in the B-tree  ​      // helper B-tree node data type      private static final class Node     {          private int m;                             // number of children          private Entry[] children = new Entry[M];   // the array of children  ​          // create a node with k children          private Node(int k)         {              m = k;         }     }  ​      // internal nodes: only use key and next      // external nodes: only use key and value      private static class Entry     {          private Comparable key;          private Object val;          private Node next;     // helper field to iterate over array entries          public Entry(Comparable key, Object val, Node next)         {              this.key  = key;              this.val  = val;              this.next = next;         }     }  ​      /**       * Initializes an empty B-tree.       */      public BTree()     {          root = new Node(0);     }  ​      /**       * Returns true if this symbol table is empty.       * @return {@code true} if this symbol table is empty; {@code false} otherwise       */      public boolean isEmpty()     {          return size() == 0;     }  ​      /**       * Returns the number of key-value pairs in this symbol table.       * @return the number of key-value pairs in this symbol table       */      public int size()     {          return n;     }  ​      /**       * Returns the height of this B-tree (for debugging).       *       * @return the height of this B-tree       */      public int height()     {          return height;     }  ​  ​      /**       * Returns the value associated with the given key.       *       * @param key the key       * @return the value associated with the given key if the key is in the symbol table       *         and {@code null} if the key is not in the symbol table       * @throws NullPointerException if {@code key} is {@code null}       */      public Value get(Key key)     {          if (key == null)         {              throw new NullPointerException("key must not be null");         }          return search(root, key, height);     }  ​      @SuppressWarnings("unchecked")      private Value search(Node x, Key key, int ht)     {          Entry[] children = x.children;  ​          // external node到最底層葉子結點,遍歷          if (ht == 0)         {              for (int j = 0; j < x.m; j++)             {                  if (eq(key, children[j].key))                 {                      return (Value) children[j].val;                 }             }         }  ​          // internal node遞迴查詢next地址          else         {              for (int j = 0; j < x.m; j++)             {                  if (j+1 == x.m || less(key, children[j+1].key))                 {                      return search(children[j].next, key, ht-1);                 }             }         }          return null;     }  ​  ​      /**       * Inserts the key-value pair into the symbol table, overwriting the old value       * with the new value if the key is already in the symbol table.       * If the value is {@code null}, this effectively deletes the key from the symbol table.       *       * @param key the key       * @param val the value       * @throws NullPointerException if {@code key} is {@code null}       */      public void put(Key key, Value val)     {          if (key == null)         {              throw new NullPointerException("key must not be null");         }          Node u = insert(root, key, val, height); //分裂後生成的右結點          n++;          if (u == null)         {              return;         }  ​          // need to split root重組root          Node t = new Node(2);          t.children[0] = new Entry(root.children[0].key, null, root);          t.children[1] = new Entry(u.children[0].key, null, u);          root = t;          height++;     }  ​      private Node insert(Node h, Key key, Value val, int ht)     {          int j;          Entry t = new Entry(key, val, null);  ​          // external node外部結點,也是葉子結點,在樹的最底層,存的是內容value          if (ht == 0)         {              for (j = 0; j < h.m; j++)             {                  if (less(key, h.children[j].key))                 {                      break;                 }             }         }  ​          // internal node內部結點,存的是next地址          else         {              for (j = 0; j < h.m; j++)             {                  if ((j+1 == h.m) || less(key, h.children[j+1].key))                 {                      Node u = insert(h.children[j++].next, key, val, ht-1);                      if (u == null)                     {                          return null;                     }                      t.key = u.children[0].key;                      t.next = u;                      break;                 }             }         }  ​          for (int i = h.m; i > j; i--)         {              h.children[i] = h.children[i-1];         }          h.children[j] = t;          h.m++;          if (h.m < M)         {              return null;         }          else         { //分裂結點              return split(h);         }     }  ​      // split node in half      private Node split(Node h)     {          Node t = new Node(M/2);          h.m = M/2;          for (int j = 0; j < M/2; j++)         {              t.children[j] = h.children[M/2+j];         }          return t;     }  ​      /**       * Returns a string representation of this B-tree (for debugging).       *       * @return a string representation of this B-tree.       */      public String toString()     {          return toString(root, height, "") + "\n";     }  ​      private String toString(Node h, int ht, String indent)     {          StringBuilder s = new StringBuilder();          Entry[] children = h.children;  ​          if (ht == 0)         {              for (int j = 0; j < h.m; j++)             {                  s.append(indent + children[j].key + " " + children[j].val + "\n");             }         }          else         {              for (int j = 0; j < h.m; j++)             {                  if (j > 0)                 {                      s.append(indent + "(" + children[j].key + ")\n");                 }                  s.append(toString(children[j].next, ht-1, indent + "     "));             }         }          return s.toString();     }  ​  ​      // comparison functions - make Comparable instead of Key to avoid casts      private boolean less(Comparable k1, Comparable k2)     {          return k1.compareTo(k2) < 0;     }  ​      private boolean eq(Comparable k1, Comparable k2)     {          return k1.compareTo(k2) == 0;     }  ​  }

B+ 樹

在瞭解完成B樹以後我們就來講講看B+樹

B+ 樹的操作

查詢

首先,B+樹的查詢和B樹一樣,類似於二叉查詢樹。起始於根節點,自頂向下遍歷樹,選擇其分離值在要查詢值的任意一邊的子指標。在節點內部典型的使用是二分查詢來確定這個位置。

結合我們的衛星資料的概念,我們再一次剖析一下B+樹的查詢

B+樹的優勢在於查詢效率和穩定性

  • B+ 樹中間節點沒有衛星資料(索引元素所指向的資料記錄),只有索引,而B樹每個結點中的每個關鍵字都有衛星資料;這就意味著同樣的大小的磁碟頁B+樹可以容納更多節點元素。在相同的資料量下,B+ 樹更加“矮胖”,IO操作更少。
  • B樹的查詢效能並不穩定(最好情況只查詢根節點,最壞情況是查詢葉子節點)。而B+樹的每一次查詢都是穩定的,每次都是根據索引查詢到葉子。

單行查詢

一般的查詢和B樹並沒有太大區別,只是B+樹要找到連結串列為止。

在 「AVL樹 vs B樹 vs B+樹」一章中我們講了B+樹更便於範圍查詢,於是我們接著就來講範圍查詢

範圍查詢

  • B樹的範圍查詢

    > 查詢範圍:[3, 9]
    
    > 方式:利用平衡樹中序遍歷有序的性質。
    

    自定向下,查詢到範圍下限 3

    image-20220922135658901

    中序遍歷到5

    image-20220922135950283

    中序遍歷到6

    image-20220922140017888

    中序遍歷到8

    image-20220922140043155

    中序遍歷到上限9,結束

    image-20220922140122920

  • B+ 樹的範圍查詢

    > 查詢範圍:[3, 9]
    

    自定向下,查詢到範圍下限 3

    image-20220922140254423

    通過連結串列指標,遍歷到9

    image.png 所以這裡就能很清楚的理解為什麼說B+樹更加適合範圍查詢了。

B+ 樹程式碼實現

本篇程式碼引用自: https://blog.csdn.net/nandao158/article/details/115701213

java  public class CatalogBTree<Key extends Comparable<Key>, Value> {        //引數M 定義每個節點的連結數      private static final int M = 4;        private Node root;        //樹的高度 最底層為0 表示外部節點   根具有最大高度,此高度是根之後的高度      private int height;        //鍵值對總數      private int n;        //節點資料結構定義      private static final class Node{          //值的數量          private int m;          private Entry[] children = new Entry[M];          private Node(int k){              m = k;         }     }        //節點內部每個資料項定義      private static class Entry{          private Comparable key;          private final Object val;          //下一個節點          private Node next;          public Entry(Comparable key, Object val, Node next){              this.key = key;              this.val = val;              this.next = next;         }          @Override          public String toString() {              StringBuilder builder = new StringBuilder();              builder.append("Entry [key=");              builder.append(key);              builder.append("]");              return builder.toString();         }       }        public CatalogBTree(){          root = new Node(0);     }        public int size(){          return n;     }        public boolean isEmpty(){          return size() == 0;     }        public int height(){          return height;     }        /**       * 查詢介面       * @param key       * @return       */      public Value get(Key key){          return search(root, key, height);     }        private Value search(Node x, Key key, int ht) {          Entry[] children = x.children;//首次進入,相當於根節點          //外部節點 這裡使用順序查詢          //如果M很大 可以改成二分查詢          if(ht == 0){//到了有資料的子節點(也可能是根節點,如果鍵值對小於M),此次查詢資料。              for(int j=0; j<x.m; j++){                  if(equal(key, x.children[j].key))//遍歷查詢                      return (Value)children[j].val;             }         }          //內部節點 尋找下一個節點          else{              for(int j=0; j<x.m; j++){                  //最後一個節點 或者 插入值小於某個孩子節點值                  if(j+1==x.m || less(key, x.children[j+1].key))//定位資料在哪個節點下,然後繼續遞迴查詢                      return search(x.children[j].next, key, ht-1);//去下一層繼續查詢             }         }          return null;     }        /**       * 新增資料介面       * @param key       * @param val       */      public void put(Key key, Value val){          //插入後的節點,如果節點分裂,則返回分裂後產生的新節點          Node u = insert(root, key, val, height);          n++;//鍵值對總數加一          if(u == null) return;//根節點沒有分裂 直接返回          //分裂根節點,已滿節點進行分裂,將已滿節點後M/2節點生成一個新節點,並將新節點的第一個元素指向父節點,此處是M>>1 = 2(因為M=4)          Node t = new Node(M>>1);          //舊根節點第一個孩子和新分裂節點第一個孩子 共同 組成新節點作為根          t.children[0] = new Entry(root.children[0].key, null, root);          t.children[1] = new Entry(u.children[0].key, null, u);          root = t;//新的根節點          height++;//節點高度加1     }        private Node insert(Node h, Key key, Value val, int ht) {          int j;          //新建待插入資料資料項          Entry t = new Entry(key, val, null);          if(ht == 0){//高度為零時,直接遍歷              for(j=0; j<h.m; j++){ // 外部節點 找到帶插入的節點位置j                  if(less(key, h.children[j].key))                      break;             }         }else{              //內部節點 找到合適的分支節點              for(j=0; j<h.m; j++){                  if(j+1==h.m || less(key, h.children[j+1].key)){                      Node u = insert(h.children[j++].next, key, val, ht-1);                      if(u == null) return null;                      t.key = u.children[0].key;                      t.next = u;                      break;                 }             }         }          //j為帶插入位置,將順序陣列j位置以後後移一位(從後往前處理) 將t插入          for(int i=h.m; i>j; i--){              h.children[i] = h.children[i-1];         }          System.out.println(j + t.toString());          h.children[j] = t;//此處插入成功          h.m++;//值的數量加一          if(h.m < M) return null;              //如果節點已滿 則執行分類操作(從根節點開始)          else return split(h);     }        private Node split(Node h) {          //將已滿節點h的後,一般M/2節點後的節點分裂到新節點並返回          Node t = new Node(M/2);          h.m = M / 2;          for(int j=0; j<M/2; j++){              t.children[j] = h.children[M/2+j];//把h節點中M/2節點後的節點分裂到新節點              h.children[M/2+j] = null;//把h節點中M/2節點後的節點設定為空,以儘快GC         }          return t;//返回新節點     }        /**       * 刪除資料       * @param key       */      public void remove(Key key){          remove(root, key, height);       }        private void remove(Node x, Key key, int ht){          Entry[] children = x.children;//首次進入,相當於根節點          //外部節點 這裡使用順序查詢          //如果M很大 可以改成二分查詢          if(ht == 0){//到了有資料的子節點(也可能是根節點,如果鍵值對小於M),此次查詢資料。              for(int j=0; j<x.m; j++){                  if(equal(key, x.children[j].key)){//遍歷查詢                      children[j] = null;//刪除此節點資料                      x.m--;//值的數量減一                 }             }         }          //內部節點 尋找下一個節點          else{              for(int j=0; j<x.m; j++){                  //最後一個節點 或者 插入值小於某個孩子節點值                  if(j+1==x.m || less(key, x.children[j+1].key))//定位資料在哪個節點下,然後繼續遞迴查詢                       remove(x.children[j].next, key, ht-1);//去下一層繼續查詢             }         }     }        private boolean equal(Comparable k1, Comparable k2){          return k1.compareTo(k2)==0;     }        private boolean less(Comparable k1, Comparable k2){          return k1.compareTo(k2)<0;     }        public String toString() {          return toString(root, height, "") + "\n";     }        private String toString(Node h, int ht, String indent) {          StringBuilder s = new StringBuilder();          Entry[] children = h.children;//此資料相當於根節點            //外部節點          if (ht == 0) {              for (int j = 0; j < h.m; j++) {                  s.append(indent + children[j].key + " " + children[j].val + "\n");             }         }          else {              for (int j = 0; j < h.m; j++) {                  s.append(indent + "(" + children[j].key + ")\n");                  s.append(toString(children[j].next, ht-1, indent + "     "));             }         }          return s.toString();     }    }

功能測試

本篇程式碼引用自:

https://github.com/tclxspy/Articles/blob/master/algorithm/MD/%E7%AE%97%E6%B3%95%2316--B%E6%A0%91%E5%AE%8C%E6%95%B4%E4%BB%A3%E7%A0%81Java%E5%AE%9E%E7%8E%B0.md

https://blog.csdn.net/nandao158/article/details/115701213

B 樹

測試建樹:

java  public class TestBTree {      @Test      public void testCreateTree(){          BTree<String, String> st = new BTree<String, String>();  ​          st.put("www.cs.princeton.edu", "128.112.136.12");          st.put("www.cs.princeton.edu", "128.112.136.11");          st.put("www.princeton.edu",    "128.112.128.15");          st.put("www.yale.edu",         "130.132.143.21");          st.put("www.simpsons.com",     "209.052.165.60");          st.put("www.apple.com",        "17.112.152.32");          st.put("www.amazon.com",       "207.171.182.16");          st.put("www.ebay.com",         "66.135.192.87");          st.put("www.cnn.com",          "64.236.16.20");          st.put("www.google.com",       "216.239.41.99");          st.put("www.nytimes.com",      "199.239.136.200");          st.put("www.microsoft.com",    "207.126.99.140");          st.put("www.dell.com",         "143.166.224.230");          st.put("www.slashdot.org",     "66.35.250.151");          st.put("www.espn.com",         "199.181.135.201");          st.put("www.weather.com",      "63.111.66.11");          st.put("www.yahoo.com",        "216.109.118.65");  ​  ​          System.out.println("cs.princeton.edu: " + st.get("www.cs.princeton.edu"));          System.out.println("hardvardsucks.com: " + st.get("www.harvardsucks.com"));          System.out.println("simpsons.com:     " + st.get("www.simpsons.com"));          System.out.println("apple.com:         " + st.get("www.apple.com"));          System.out.println("ebay.com:         " + st.get("www.ebay.com"));          System.out.println("dell.com:         " + st.get("www.dell.com"));          System.out.println();  ​          System.out.println("size:   " + st.size());          System.out.println("height: " + st.height());          System.out.println(st);          System.out.println();     }  }

測試結果:

java  cs.princeton.edu:  128.112.136.12  hardvardsucks.com: null  simpsons.com:      209.052.165.60  apple.com:         17.112.152.32  ebay.com:          66.135.192.87  dell.com:          143.166.224.230  ​  size:    17  height:  2            www.amazon.com 207.171.182.16            www.apple.com 17.112.152.32            www.cnn.com 64.236.16.20       (www.cs.princeton.edu)            www.cs.princeton.edu 128.112.136.12            www.cs.princeton.edu 128.112.136.11            www.dell.com 143.166.224.230  (www.ebay.com)            www.ebay.com 66.135.192.87            www.espn.com 199.181.135.201            www.google.com 216.239.41.99       (www.microsoft.com)            www.microsoft.com 207.126.99.140            www.nytimes.com 199.239.136.200  (www.princeton.edu)            www.princeton.edu 128.112.128.15            www.simpsons.com 209.052.165.60       (www.slashdot.org)            www.slashdot.org 66.35.250.151            www.weather.com 63.111.66.11       (www.yahoo.com)            www.yahoo.com 216.109.118.65            www.yale.edu 130.132.143.21

B+ 樹

測試建樹:

java  public class TestCatalogBTree {  ​      @Test      public void testCreateTree(){          /**           * 新增的順序不同,最後樹的結構也不同           */          CatalogBTree<Integer,String> bt = new CatalogBTree<>();          bt.put(5,"a");          bt.put(8,"b");          //     bt.put(9,"c");          bt.put(10,"d");          bt.put(15,"e");          //     bt.put(18,"f");          bt.put(20,"g");          bt.put(26,"h");          //     bt.put(27,"i");  ​          bt.put(28,"i");          bt.put(30,"j");          //     bt.put(33,"k");          bt.put(35,"l");          bt.put(38,"m");          //   bt.put(50,"n");          bt.put(56,"o");          bt.put(60,"p");          //     bt.put(63,"q");  ​          bt.put(65,"r");          bt.put(73,"s");          //       bt.put(79,"t");          bt.put(80,"u");          bt.put(85,"v");          //   bt.put(88,"w");          bt.put(90,"x");          bt.put(96,"y");          bt.put(99,"z");  ​  ​          /**           * 插入第三個元素           */          bt.put(9,"c");          bt.put(18,"f");          bt.put(27,"i");          bt.put(33,"k");          bt.put(50,"n");          bt.put(63,"q");          bt.put(79,"t");          bt.put(88,"w");  ​          System.out.println("高度:"+bt.height());          System.out.println("查詢:"+bt.get(9));          System.out.println( bt.toString());     }  ​  }  ​

測試結果:

java  0Entry [key=5]  1Entry [key=8]  2Entry [key=10]  3Entry [key=15]  2Entry [key=20]  3Entry [key=26]  2Entry [key=20]  2Entry [key=28]  3Entry [key=30]  3Entry [key=28]  2Entry [key=35]  3Entry [key=38]  2Entry [key=35]  2Entry [key=56]  3Entry [key=60]  3Entry [key=56]  2Entry [key=35]  2Entry [key=65]  3Entry [key=73]  2Entry [key=65]  2Entry [key=80]  3Entry [key=85]  3Entry [key=80]  3Entry [key=65]  2Entry [key=90]  3Entry [key=96]  2Entry [key=90]  2Entry [key=99]  2Entry [key=9]  2Entry [key=18]  2Entry [key=27]  2Entry [key=33]  2Entry [key=50]  2Entry [key=63]  2Entry [key=79]  2Entry [key=88]  高度:3  查詢:c  (5)       (5)           (5)                 5 a                 8 b                 9 c           (10)                 10 d                 15 e                 18 f       (20)           (20)                 20 g                 26 h                 27 i           (28)                 28 i                 30 j                 33 k  (35)       (35)           (35)                 35 l                 38 m                 50 n           (56)                 56 o                 60 p                 63 q       (65)           (65)                 65 r                 73 s                 79 t           (80)                 80 u                 85 v                 88 w           (90)                 90 x                 96 y                 99 z

小結

不得不說,B樹以及B+樹的內容還是挺多的,寫這篇文章也花了我挺多精力和時間的。不過看完這篇文章以後,面對面試官 ”說說看B或B+樹吧“ 的問題,應該是有得一聊了。

本篇程式碼已同步上傳至我的開源倉庫:https://github.com/pixel-revolve/forest

本文參考: