definition
In computer science, a B-tree is a self-balancing tree that keeps data in order. This data structure allows the searching of data, sequential access, inserting data and deleting operations to be completed in logarithmic time.
Why introduce B-tree?
First of all, including the red and black tree we introduced earlier, is an internal search tree that stores input into memory .
B-tree is an extension of the previous balance tree algorithm. It supports external searches for symbol tables saved on disk or network . These files may be much larger than the input we considered before (hard to store in memory).
Since the content is stored on disk, the disk I/O read and write too frequently due to the large depth of the tree (the disk read and write rate is limited), which leads to inefficient query efficiency.
Then it is naturally important to reduce the depth of the tree. Therefore, we introduce B-tree, multiple-way search tree.
Features
Each node in the tree contains at most m children (m>=2);
Except for the root node and leaf node, each node has at least [ceil(m/2)] children (where ceil(x) is a function that takes the upper limit);
If the root node is not a leaf node, there will be at least 2 children (special case: there is no root node for children, that is, the root node is a leaf node, and the whole tree has only one root node);
All leaf nodes appear in the same layer (bottom layer), and the leaf nodes are external nodes, which save the content, namely key and value .
Other nodes are internal nodes, which save the index, namely key and next .
Keywords of internal nodes: K[1], K[2], …, K[M-1]; and K[i] < K[i+1];
Pointers next to the content node: P[1], P[2], …, P[M]; where P[1] points to a subtree with the keyword less than K[1], P[M] points to a subtree with the keyword greater than K[M-1], and other P[i] points to a subtree with the keyword (K[i-1], K[i]);
For example: (M=3)
Find and insert
For convenience, a special sentinel key is used here, which is smaller than all other keys and is represented by *.
At the beginning, the B-tree only contains one root node, and the root node only contains the sentinel key when initialized.
Each key in an internal node is associated with a node. All keys are greater than or equal to the key associated with this node, but smaller than all other keys.
These conventions can greatly simplify the code.
Code
Click to download.
This code implementation introduces the sentinel key, and the code output eliminates it.
The B-tree with the sentinel key in the code (save the image locally to view, and the words will be clearer):
The B-tree output by the code (save the image locally to view, and the words will be clearer):
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 to the lowest leaf node, traverse if (ht == 0) { for (int j = 0; j < xm; j++) { if (eq(key, children[j].key)) { return (Value) children[j].val; } } } // internal node recursively searches next address else { for (int j = 0; j < xm; j++) { if (j+1 == xm || 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); // The right node generated after split n++; if (u == null) { return; } // need to split root reorganization 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 external node, which is also a leaf node. At the bottom of the tree, the content value is stored if (ht == 0) { for (j = 0; j < hm; j++) { if (less(key, h.children[j].key)) { break; } } } // The internal node inside the node is the next address else { for (j = 0; j < hm; j++) { if ((j+1 == hm) || 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 = hm; i > j; i--) { h.children[i] = h.children[i-1]; } h.children[j] = t; h.m++; if (hm < M) { return null; } else { //Split node return split(h); } } // split node in half private Node split(Node h) { Node t = new Node(M/2); hm = 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 < hm; j++) { s.append(indent + children[j].key + " " + children[j].val + "/n"); } } else { for (int j = 0; j < hm; 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("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
The above is all the content of this article. I hope it will be helpful to everyone's learning and I hope everyone will support Wulin.com more.