Definition

In computer science, B-tree (English: B-tree) is a self-balancing tree that can maintain data in order. This data structure allows the operations of searching for data, sequential access, inserting data, and deleting data to be completed in logarithmic time.

Why introduce B-tree63;

Firstly, including the red-black tree we introduced earlier, input is stored intomemoryainternal search tree。

B-tree is an extension of the previous balanced tree algorithm, which supports storingdisk or networksymbol tableExternal lookupThese files may be much larger than the input we have considered before (difficult to store in memory).

Since the content is stored on disk, it will naturally cause disk I/Frequent read and write operations (disk read and write speeds are limited) can lead to low query efficiency.

Therefore, reducing the depth of the tree is naturally very important. Therefore, we introduce the B-tree, a multi-way search tree.

characteristics

Each node in the tree can have at most m children (m>=2);

Except for the root and leaf nodes, each node has at least [ceil(m / 2children (where ceil(x) is an upper bound function);

If the root node is not a leaf node, then there are at least2children (special case: the root node has no children, i.e., the root node is a leaf node, and the entire tree has only one root node);

All leaf nodes appear on the same level (the lowest level),Leaf nodes are external nodes, which store content, i.e., key and value。

Other nodes are internal nodes, which store indexes, i.e., key and next。

key of internal node: K[1], K[2], ..., K[M-1]; and K[i] < K[i+1];

pointer to content node next: P[1], P[2], ..., P[M]; where P[1], K[i] less than K[1], K[i] subtree, P[M] points to keywords greater than K[M-1], K[i] belongs to (K[i-1], K[i]) subtree;

For example: (M=3)

search and insert

For convenience, a special sentinel key is used here, which is less than all other keys, using*means.

Initially, the B-tree contains only one root node, and the root node only contains the sentinel key at initialization.

Each key in the internal nodes is associated with a node, and the subtree rooted at this node, where all keys are greater than or equal to the key associated with this node, but less than all other keys.

These conventions can greatly simplify the code.

code

Click to download.

This code implementation introduces sentinel keys, but they are excluded from the output.

The B-tree containing sentinel keys in the code (save the image locally to see the text more clearly):

The B-tree output by the code (save the image locally to see the text more clearly):

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 null if the key is not in the symbol table
   * @throws NullPointerException if key is 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 to the bottommost leaf node, traverse
    if (ht == 0) 
    {
      for (int j = 0; j < x.m; j++)       
      {
        if (eq(key, children[j].key)) 
        {
          return (Value) children[j].val;
        }
      }
    }
    // internal node recursively searches the next address
    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 null, this effectively deletes the key from the symbol table.
   *
   * @param key the key
   * @param val the value
   * @throws NullPointerException if key is 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); //right node generated after splitting
    n++;
    if (u == null) 
    {
      return;
    }
    // need to split root, reorganize 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, also a leaf node, at the bottom of the tree, stores content value
    if (ht == 0) 
    {
      for (j = 0; j < h.m; j++) 
      {
        if (less(key, h.children[j].key)) 
        {
          break;
        }
      }
    }
    // internal node, stores next address
    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     
    {  //Splitting node
      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;
  }
  /**
   * Unit tests the {@code BTree} data type.
   *
   * @param args the command-line arguments
   */
  public static void main(String[] args) 
  {
    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();
  }
}

Output:
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

That's all for this article. Hope it helps everyone's learning and also hope everyone will support the Shouting Tutorial.

Statement: The content of this article is from the Internet, and the copyright belongs to the original author. The content is contributed and uploaded by Internet users spontaneously. This website does not own the copyright, has not been edited by humans, and does not assume any relevant legal liability. If you find any content suspected of copyright infringement, please send an email to: notice#oldtoolbag.com (when sending an email, please replace # with @ to report, and provide relevant evidence. Once verified, this site will immediately delete the content suspected of infringement.)