B树(B-树)

作者: 我是小曼巴 | 来源:发表于2020-04-20 20:20 被阅读0次

B+树和B树的区别
B树、B+树、B*树
B树、B+树、B*树
B-/B+树看 MySQL索引结构
转：B树
B-树/B+树
对B+树，B树，红黑树的理解
[数据库之十] 数据库索引之B-、B+树索引
B-树
B-树

说明

B树，也写作B-树，两者是同一种树，都读作B树（这里的-是英文连接符并不是减号，千万不要读成B减树）。

概念

前面介绍的AVL树、红黑树都是带平衡条件的二叉查找树，每个节点最多可有2个分支；而B树属于平衡多叉查找树，一棵阶为M的B树，每个中间节点（非根、非叶）最多可有M个分支；在二叉查找树中，需要一个关键字来决定两个分支到底取哪个分支；而在M叉查找树中需要M-1个关键字来决定选取哪个分支。一棵完全二叉树的高度约为 $log_{2}N$ ，而一棵完全M叉树的高度大约是 $log_{M}N$ 。

B树的主要价值是存储数据，以便在面向块的存储环境中高效检索——特别是文件系统，它能有效地减低磁盘操作的次数；数据库索引技术里大量使用B树和B+树的数据结构；

因为如果数据量太大，导致不能把整个数据结构存储到计算机的主存中，那么意味着必须把数据存放到磁盘上，此时，评判一个操作的时间复杂度，大O模型已经不再适用，因为大O模型假设所有的操作耗时相等。然而，涉及磁盘IO操作时，因为磁盘IO的耗时远远大于内存操作，我们所要做的就是把磁盘访问次数减少到一个非常小的常数，比如3或4。

性质

阶为M的B树是一颗具有下列特性的树：

1.中间节点（除根节点、叶子节点）的儿子数量在 $\left \lceil M/2 \right \rceil$ 和 $M$ 之间，关键字数量在 $\left \lceil M/2 \right \rceil-1$ 和 $M-1$ 之间，即处于半满状态。

2.若根节点不是叶子节点，那么根节点至少有两颗子树。

3.所有的叶子节点都在相同的深度上。

4.每个节点包含的数据有关键字（ $K_{1},K_{2},...,K_{n}$ ，n为关键字数量）、关键字记录的指针、儿子节点的链接（ $L_{0},L_{1},...,L_{n}$ ）。每个节点内关键字从小到大按序存储。

$K_{i}$ 关键字的左边的链接为 $L_{i-1}$ ，其指向的儿子节点中的所有关键字皆小于 $K_{i}$ ；
$K_{i}$ 关键字的右边的链接为 $L_{i}$ ，其指向的儿子节点中的所有关键字皆大于 $K_{i}$ 。

特别说明：
a.B树的每个节点可以看做文件系统的一个区块（block）,关键字记录的指针、儿子节点的链接实际上就是指向另一个block的地址。
b.B树的叶子节点除了包含了关键字、关键字记录的指针外，也有指向其子节点的指针，只不过其指针地址都为null。
c.B树的叶子节点包含的关键字数量可以不同于中间节点，假设叶子节点的关键字数量在 $\left \lceil L/2 \right \rceil-1$ 和 $L-1$ 之间， $L$ 可以不同于 $M$ 。但是一般情况下，L和M默认相等，后面的例子中也是默认相等。
d.实际情况中，M如何取值：已知文件系统的最小存储单位是block，为4096字节；假设一个节点对应一个block，地址指针大小为4字节，关键字大小为32字节，于是计算M： $（M-1）*32 +（M-1）*4 + M*4<=4096$ ，则M取最大的103。所以M的取值一般来说是固定的，跟数据表中的记录数无关；有时候面试官会问如果有2000万行数据，你的M值怎么确定？其实是个陷阱，无论你存取多少数据，M的值当然是越大越好，而M又不能无限大，一般根据block的大小，就可以计算出上限值，取上限值即可。一般情况下，MySQL的性能在数据量不超过1000万行时性能最佳，因为此时B+树的高度在3~5。

下图显示一棵5阶B树，即M为5。所有的非叶子节点的儿子数都在3和5之间，从而有2到4个关键字；L也为5，因此每片树叶有2到4个关键字。要求这些节点半满将保证B树不会退化成简单的二叉树。图中数字代表关键字，红色箭头代表关键字记录指针，黑色箭头代表儿子节点链接。后面为了方便，关键字记录指针就不画出来了。

图1：5阶B树

插入操作

例子1
定义一个5阶B树，现在我们要把3、8、31、11、23、29、50、28 这些数字构建出一个5阶树出来，通过依次插入这些关键字，遵循规则：
（1）节点拆分规则：当前是要构建5叉查找树，那么此时M=5，每个节点的关键字数必须满足半满状态，即2～4个，所以关键字数大于4时需要对节点进行拆分；
（2）排序规则：节点内的关键字需要依序存储；

图2：依次插入3、8、31、11、23、29、50、28，构建B树

例子2
设想现在要把57插入到图1的5阶B树中，我们看看实际的操作流程。
（1）内存中保留B树的根节点的磁盘地址，通过第一次磁盘操作读取根节点block的内容到内存中：

通过折半查找发现，57应该位于第二个指针对应的子树中，此时通过第二个指针读取对应内容。
（2）通过第二次磁盘操作读取对应节点的内容到内存中：

通过折半查找发现，57应该位于第四个指针对应的子树中，此时通过第四个指针读取对应内容。
（3）通过第三次磁盘操作读取对应节点的内容到内存中：

通过折半查找发现57应该位于第二个指针对应的子树当中，但发现第二个指针为null，即已经到达叶子节点（叶子节点中的指针全为空），所以此时应该直接进行磁盘写操作。而此时的叶子节点并没有满员，所以直接写入即可。最后的结果如下图所示。

图3：插入57

整个插入过程经历3次磁盘读操作和1次磁盘写操作，其中内存中的计算相比磁盘操作，可以忽略不计。

例子3
设现在要往图3所示的B树中插入55，那么将会有一个问题：55想要插入的那片树叶已经满了。此时通过节点分裂的方式，将插入的那片树叶分裂成两片树叶。写这两片树叶需要2次磁盘访问，更新它们的父节点需要第3次磁盘访问。最后得到的树如图4-62所示。虽然分裂节点是耗时的，因为它至少需要2次附加的磁盘写，但它相对很少发生。

图4：插入55

例子4
前面例子中的节点分裂之所以行的通是因为其父节点的儿子个数尚未满员，如果满员，我们的做法如下。例如，假设我们想要把40（bug:这里的40改为41.5，后同）插入到图4所示的树中。在插入40时，叶子节点需要进行分裂，其父节点的儿子数将达到6个，这是不允许的。此时的做法是，将父节点进行分裂，同时更新父节点的关键字以及父节点的父亲的值，这样也会导致额外的两次磁盘写。结果下图所示。

图5：插入40

正如此处的情形所示，当一个非叶节点分裂时，它的父节点得到一个儿子。如果父节点的儿子个数已经达到规定的限度，那么继续沿树向上分裂节点直到找到一个不需要再分裂的父节点，或者达到树根。如果到达树根，那么树根分裂成两个节点，然后新建一个新的树根，将原树根分裂的两个节点当做新的树根的2个儿子，此时，树的高度增加了1。这就是为什么准许树根可以最少有两个儿子的原因所在。

注：B*树的做法与B树不同：即在相邻节点有空间时，把一个关键字交给该相邻节点领养。

删除操作

我们可以通过查找要删除的项并在找到后删除它来执行删除操作。问题在于，如果被删元所在的树叶的关键字数量已经是最小值，那么删除后它的数量就低于最小值了。我们可以通过在相邻节点本身没有达到最小值时领养一个邻项来矫正这种情况。如果相邻节点已经达到最小值，那么可以与该相邻节点合并形成一片满叶。这会使得其父节点失去一个儿子，如果失去儿子的结果又引起父节点的儿子数低于最小值，那么使用相同的策略继续进行，这个过程可以一直上溯到根。如果这个领养过程的结果使得根只剩下一个儿子，那么删除根，并让根的这个儿子作为树的新根，此时树的高度就降1。

例如，假设我们要从图5中删除99，由于那片叶子节点将只剩一个关键字，而它的邻居也已经是最小值2项了，因此我们把这些项合并成有4项的一片新的树叶。结果它的父节点只有2个儿子节点（1个关键字），不满足半满规则。此时该父节点可以从它的邻节点领养一个儿子（以及对应的关键字），因为邻节点有4个儿子。领养的结果使得双方都有3个儿子，结果如图6所示。

图6：删除99

查找操作

在上面的插入和删除操作中，已经介绍了查找操作。此处要说明的是，B树的查找操作可能在非叶子节点就命中记录，比如在图6中查找54元素，在第二层就已经命中。

磁盘和文件系统

磁盘的最小存储单位就是扇区（sector）了，一般情况每个扇区512字节。
7200RPM转速的磁盘，一转需要8.3ms，一般可以将一次磁盘IO的时间看做10ms。
文件系统进行文件存取的最小单位是块（block），ext3/ext4的文件系统，默认的block size是4096字节，由连续的8个扇区组成。

相关代码

B数节点定义：

    public class Node<K, V> {

        // 节点内的项:根据K排序的有序链表
        private List<Entry<K, V>> entrys;

        // 节点的孩子节点
        private List<Node<K, V>> sons;

        // 是否是叶子节点
        private boolean isLeaf;

        // 键值比较函数对象, 如果采用倒序或者其它排序方式, 传入该对象
        private Comparator<K> kComparator;

        Node() {
            this.entrys = new LinkedList<Entry<K, V>>();
            this.sons = new LinkedList<Node<K, V>>();
            this.isLeaf = false;
        }

        Node(Comparator<K> kComparator) {
            this();
            this.kComparator = kComparator;
        }

        private int compare(K key1, K key2) {
            return this.kComparator == null ? ((Comparable<K>) key2).compareTo(key1) : kComparator.compare(key1, key2);
        }

        public boolean getIsLeaf() {
            return this.isLeaf;
        }

        public void setIsLeaf(boolean isLeaf) {
            this.isLeaf = isLeaf;
        }

        public int nodeSize() {
            return this.entrys.size();
        }

        // 有序链表的二分查找
        public SearchResult<V> search(K key) {
            int begin = 0;
            int end = this.nodeSize() - 1;
            int mid = (begin + end) / 2;
            boolean isExist = false;
            int index = 0;
            V value = null;
            while (begin < end) {
                mid = (begin + end) / 2;
                Entry midEntry = this.entrys.get(mid);
                int compareRe = compare((K) midEntry.getKey(), key);
                if (compareRe == 0) {
                    break;
                } else {
                    if (compareRe > 0) {
                        begin = mid + 1;
                    } else {
                        end = mid - 1;
                    }
                }
            }
            if (begin < end) {
                isExist = true;
                index = mid;
                value = this.entrys.get(mid).getValue();
            } else if (begin == end) {
                K midKey = this.entrys.get(begin).getKey();
                int comRe = compare(midKey, key);
                if (comRe == 0) {
                    isExist = true;
                    index = begin;
                    value = this.entrys.get(mid).getValue();
                } else if (comRe > 0) {
                    isExist = false;
                    index = begin + 1;
                    value = null;
                } else {
                    isExist = false;
                    index = begin;
                    value = null;
                }
            } else {
                isExist = false;
                index = begin;
                value = null;
            }
            return new SearchResult<V>(isExist, index, value);
        }

        // 删除给定索引位置的项
        public Entry<K, V> removeEntry(int index) {
            Entry<K, V> re = this.entrys.get(index);
            this.entrys.remove(index);
            return re;
        }

        // 得到index处的项
        public Entry<K, V> entryAt(int index) {
            return this.entrys.get(index);
        }

        // 将新项插入指定位置
        private void insertEntry(Entry<K, V> entry, int index) {
            this.entrys.add(index, entry);
        }

        // 节点内插入项
        private boolean insertEntry(Entry<K, V> entry) {
            SearchResult<V> result = search(entry.getKey());
            if (result.isExist()) {
                return false;
            } else {
                insertEntry(entry, result.getIndex());
                return true;
            }
        }

        // 更新项，如果项存在，更新其值并返回原值，否则直接插入
        public V putEntry(Entry<K, V> entry) {
            SearchResult<V> re = search(entry.getKey());
            if (re.isExist) {
                Entry oldEntry = this.entrys.get(re.getIndex());
                V oldValue = (V) oldEntry.getValue();
                oldEntry.setValue(entry.getValue());
                return oldValue;
            } else {
                insertEntry(entry);
                return null;
            }
        }

        // 获得指定索引的子节点
        public Node childAt(int index) {
            return this.sons.get(index);
        }

        // 删除给定索引的子节点
        public void removeChild(int index) {
            this.sons.remove(index);
        }

        // 将新的子节点插入到指定位置
        public void insertChild(Node<K, V> child, int index) {
            this.sons.add(index, child);
        }
    }

// 内部类, B树中节点中的元素. K:键类型, V:值类型,可以是指向数据的索引,也可以是实体数据
    private class Entry<K, V> {
        private K key;
        private V value;

        public K getKey() {
            return this.key;
        }

        public void setKey(K key) {
            this.key = key;
        }

        public V getValue() {
            return this.value;
        }

        public void setValue(V value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return "key: " + this.key + " , ";
        }
    }

    // 内部类, 封装搜索结果
    private class SearchResult<V> {
        private boolean isExist;
        private V value;
        private int index;

        public SearchResult(boolean isExist, int index, V value) {
            this.isExist = isExist;
            this.index = index;
            this.value = value;
        }

        public boolean isExist() {
            return isExist;
        }

        public V getValue() {
            return value;
        }

        public int getIndex() {
            return index;
        }
    }

参考博客：
https://blog.csdn.net/maxiaoyin111111/article/details/84342669
https://zhuanlan.zhihu.com/p/27700617

B+树和B树的区别
B-树 B-树概述 B-树,这里的 B 表示 balance( 平衡的意思),B-树是一种多路自平衡的搜索树（B树...
B树、B+树、B*树
B-树 B+树 B*树
B树、B+树、B*树
B-树，就是B树，B树的原英文名是B-tree,所以很多翻译为B-树,就会很多人误以为B-树是一种树、B树是另外一...
B-/B+树看 MySQL索引结构
B-树 B-树,这里的 B 表示 balance( 平衡的意思),B-树是一种多路自平衡的搜索树。它类似普通的平衡...
转：B树
1、B-树(B树)的基本概念 B-树中所有结点中孩子结点个数的最大值成为B-树的阶，通常用m表示，从查找效率考虑，...
B-树/B+树
B-树(Balance树)和B+树应用与数据库索引，是m叉的多路平衡查找树。 1. 性质分析 1.1 M阶B-树 ...
对B+树，B树，红黑树的理解
写在前面，好像不同的教材对b树，b-树的定义不一样。我就不纠结这个到底是叫b-树还是b-树了。如图所示，区别有以...
[数据库之十] 数据库索引之B-、B+树索引
一、B- 树索引 1、定义 B树也称B-树,它是一颗多路平衡查找树。我们描述一颗B树时需要指定它的阶数，阶数表...
B-树
为什么需要B-树当所有数据都存储在内存中时，用红黑树的查找性能已经非常的好了。但是当数据量非常的大的时候，把数据...
B-树
为什么需要B-树当所有数据都存储在内存中时，用红黑树的查找性能已经非常的好了。但是当数据量非常的大的时候，把数据...