本文参考链接：

从B树、B+树、B*树谈到R 树_磁盘,数据结构,存储_结构之法 算法之道-CSDN博客

【数据结构】B树、B+树详解 - Assassinの - 博客园

BTree.java

B树的由来

B树是为了磁盘或其它存储设备而设计的一种多叉平衡查找树，许多数据库系统都一般使用B树或者B树的各种变形结构，如B+树，B*树来存储信息。

在大规模的数据查找中，即使是平衡二叉树也会产生过深的深度，导致磁盘频繁存取，影响查找效率。

磁盘上数据必须用一个三维地址唯一标示：柱面号、盘面号、块号。

读/写磁盘上某一指定数据需要下面3个步骤：

1. 首先移动臂根据柱面号使磁头移动到所需要的柱面上，这一过程被称为定位或查找 。

2. 根据盘面号来确定指定盘面上的磁道。

3. 盘面确定以后，盘片开始旋转，将指定块号的磁道段移动至磁头下。

访问某一具体信息，由3部分时间组成：

• 查找时间(seek time) ：磁头移动到指定磁道的时间。这部分时间代价最高，最大可达到0.1s左右。

• 等待时间(latency time) ：磁盘旋转到指定盘块的时间。由于盘片绕主轴旋转速度很快，一般为7200转/分(电脑硬盘的性能指标之一, 家用的普通硬盘的转速一般有5400rpm(笔记本)、7200rpm几种)。因此一般旋转一圈大约0.0083s。

• 传输时间(transmission time) ：数据通过系统总线传送到内存的时间，一般传输一个字节(byte)大概0.02us=2*10^-8s

磁盘读取数据是以盘块(block)为基本单位的。位于同一盘块中的所有数据都能被一次性全部读取出来。 而磁盘IO代价主要花费在查找时间上。因此我们应该尽量将相关信息存放在同一盘块，同一磁道中。或者至少放在同一柱面或相邻柱面上，以求在读/写信息时尽量减少磁头来回移动的次数，避免过多的查找时间。

有了B树，我们就可以将节点和盘块关联起来，避免频繁进行磁盘IO访问。

B树的操作

我们用阶数m来定义一棵B树：

• 树中每个结点最多含有m个孩子（m>=2），至多有m-1个关键字（两棵子树指针夹着一个关键字）
• 除根结点和叶子结点外，其它每个结点至少有⌈m/2⌉个孩子（至少⌈m/2⌉-1个关键字，出于效率原因规定的）
• 若根结点不是叶子结点，则至少有2个孩子（至少一个关键字）
• 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息
• 一颗3阶树结构如下：

B树的搜索

B树是多路查找树,二叉排序树是二路查找,B树是多路查找,所以它是二叉排序树的拓展。因此,B树的查找操作和二叉排序树的查找操作非常类似。

查找过程:
1. 先让待查找关键字key和结点的中的关键字比较,如果等于其中某个关键字,则查找成功。
2. 如果和所有关键字都不相等,则看key处在哪个范围内,然后去对应的指针所指向的子树中查找。
Eg:如果key比第一个关键字K₁还小,则去P₀指针所指向的子树中查找,如果比最后一个关键字K_n还大,则去P_n指针所指向的子树中查找。

B树的插入

在二叉排序树中,仅需查找到需插入的终端结点的位置。但是,在B树中找到插入的位置后,并不能简单地将其添加到终端结点位置,因为此时可能会导致整棵树不再满足B树中定义中的要求。

给定一组关键字{20,30,50,52,60,68,70},给出创建一棵3阶B树的过程。

1. 由于m=3，所以除了根结点以外,非叶子结点至少有⌈3/2⌉-1=1个关键字，最多有3-1=2个关键字。
   所以依次插入20和30两个关键字到结点。
2. 接下来插入50，如下，但是由于最多有2个关键字，所以这个结点不满足B树要求，需要分裂

分裂的方法: 取这个关键字数组中的中间关键字(⌈n/2⌉)作为新的结点,然后其他关键字形成两个结点作为新结点的左右孩子。

3. 接下来插入52,,由于50结点只有一个关键字,所以可以插入52

4. 接下来插入60,插入60之后该结点关键字数量又不符合要求,需要分裂

分裂过程: 取中间关键字(⌈3/2⌉=2)52,由于根结点只含30一个关键字,可以将52和30合并到一起。
接下来需要处理50和60这两个结点,由于30<50<52,60>52,所以50和60各自单独作为一个结点。

5. 接下来插入68,由于60结点只有一个关键字,所以可以插入68

6. 接下来插入70，插入70之后该结点关键词数量又不符合要求，需要分裂。

B树的删除

B树中的删除操作与插入操作类似,但要稍微复杂些,要使得删除后的结点中的关键字个数≥⌈m/2⌉-1,因此将涉及结点的“合并问题。由于删除的关键字位置不同,可以分为关键字在终端结点和不在终端结点上两种情况。

如果在终端结点上:

1. 结点内关键字数量大于⌈m/2⌉-1,这时删除这个关键字不会破坏B树的定义要求。所以直接删除。
2. 结点内关键字数量等于⌈m/2⌉-1,并且其左右兄弟结点中存在关键字数量大于⌈m/2⌉-1的结点,则去兄弟结点中借关键字。
3. 结点内关键字数量等于⌈m/2⌉-1,并且其左右兄弟结点中不存在关键字数量大于⌈m/2⌉-1的结点,则需要进行结点合并。

如果不在终端结点上:

找出它的相邻关键字，转换成在终端结点上（交换结点）

B树的高度

log_m/2^(N+1)/2 + 1

B+树

B+树的特征：
+ 有m个子树的中间节点包含有m个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引
+ 所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。 (而B树的叶子节点并没有包括全部需要查找的信息)
+ 所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (而B树的非终节点也包含需要查找的有效信息)

为什么说B+树比B树更适合数据库索引？

1. B+树的磁盘读写代价更低

　　B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了；

2. B+树查询效率更加稳定

　　由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当；

3. B+树便于范围查询（最重要的原因，范围查找是数据库的常态）

　　B树在提高了IO性能的同时并没有解决元素遍历的时候效率低下的问题，正是为了解决这个问题，B+树应用而生。B+树只需要去遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作或者说效率太低

附：Algorithms第四版B树实现

这个B树实现非叶子节点居然不带信息，把我整懵了

public class BTree<Key extends Comparable<Key>, Value>  {
    // 度数M，一个结点最多有M-1个关键字
    private static final int M = 4;

    private Node root;       // 根节点
    private int height;      // B树的高度
    private int n;           // 该树中一共有多少个key-value对

    // 节点
    private static final class Node {
        private int m;                             // 有多少个子节点
        private Entry[] children = new Entry[M];   // 子节点的数组

        // create a node with k children
        private Node(int k) {
            m = k;
        }
    }

    // 一条索引
    // 内部节点：只使用key和next
    // 叶子节点，只使用key和value
    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;
        }
    }

    /**
     * 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 IllegalArgumentException if {@code key} is {@code null}
     */
    public Value get(Key key) {
        if (key == null) throw new IllegalArgumentException("argument to get() is null");
        return search(root, key, height);
    }

    private Value search(Node x, Key key, int ht) {
        Entry[] children = x.children;

        // 如果是叶子节点
        if (ht == 0) {
            //找到叶子节点中对应的索引项
            for (int j = 0; j < x.m; j++) {
                if (eq(key, children[j].key)) return (Value) children[j].val;
            }
        }

        // 如果不是叶子节点
        else {
            for (int j = 0; j < x.m; j++) {
                //如果是节点中最后一条索引项或者位于该索引项与下一条索引项之间
                if (j+1 == x.m || less(key, children[j+1].key))
                    //搜索该索引项的next
                    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 IllegalArgumentException if {@code key} is {@code null}
     */
    public void put(Key key, Value val) {
        if (key == null) throw new IllegalArgumentException("argument key to put() is null");
        Node u = insert(root, key, val, height);
        n++;
        if (u == null) return;

        // need to split 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
        if (ht == 0) {
            for (j = 0; j < h.m; j++) {
                if (less(key, h.children[j].key)) break;
            }
        }

        // internal node
        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;
    }
}