【高阶数据结构】B树 {B树的概念；B树的实现：节点设计，查找，插入，遍历，删除；B树的性能分析；B+树和B*树；B树的应用}

一、常见的搜索结构

以上结构适合用于数据量相对不是很大，能够一次性存放在内存中，进行数据查找的场景。如果数据量很大，比如有100G数据，无法一次放进内存中，那就只能放在磁盘上了，如果放在磁盘上，有需要搜索某些数据，那么如果处理呢？

那么我们可以考虑将存放关键字及其映射数据的地址放到一个内存中的搜索树的节点中，那么要访问数据时，先取这个地址去磁盘访问数据

使用平衡二叉搜索树的缺陷：
平衡二叉树搜索树的高度是log_2 N，这个查找次数在内存中是很快的。但是当数据都在磁盘中时，访问磁盘速度很慢，在数据量很大时，log_2 N次的磁盘访问，是一个难以接受的结果。

使用哈希表的缺陷：
哈希表的效率很高是O(1)，但是一些极端场景下某个位置冲突很多，导致访问次数剧增，也是难以接受的。

使用B树（改进平衡二叉搜索树）：

1. 压缩高度，二叉变多叉：节点可以有多个子节点。B树的一个关键特点是每个节点可以拥有多于两个的子节点，这与传统的二叉搜索树（binary search tree）不同，后者最多只能有两个子节点。
2. 一个节点中存放多个关键字及映射数据的地址：B树的节点不仅包含指向子节点的指针，还包含一个关键字列表，这些关键字用于在树中分割和排序数据。
3. 适用于外部存储。由于B树能够高效地处理大量数据，特别是当数据存储在磁盘等间接存储设备上时，B树能够减少磁盘I/O操作，因此常用于数据库和文件系统。
4. 高度较低。由于B树的特殊设计，其高度相对较低，这有助于保持操作效率。

---

二、B树的概念

1970年，R.Bayer和E.mccreight提出了一种适合外查找的树，它是一种平衡的多叉树，称为B树(后面有一个B的改进版本B+树，然后有些地方的B树写的的是B-树，注意不要误读成"B减树")。

一棵m阶(m>2)的B树，是一棵平衡的M路平衡搜索树，可以是空树或者满足一下性质：

1. 根节点至少有1个关键字，2个孩子

2. 每个分支节点都包含k-1个关键字和k个孩子，其中 ceil(m/2) ≤ k ≤ m（ceil是向上取整函数），分支节点孩子比关键字多一个。

3. 所有的叶子节点都在同一层，叶子节点只有关键字，没有孩子

4. 每个节点中的关键字从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域划分

5. 每个结点的结构为：（n，A0，K1，A1，K2，A2，… ，Kn，An）其中，Ki(1≤i≤n)为关键字，且Ki

插入过程：

1. 找到该元素的插入位置（某叶子节点中的位置）
2. 按照插入排序的思想将关键字插入到该节点的合适位置
3. 检测该节点是否满足B树的性质，满足：插入结束，不满足：对节点进行分裂

注意：新增的关键字只能插入到叶子节点，不能插入到分支节点。因为分支节点的孩子比关键字多一个，新增一个关键字就需要新增一个孩子。而叶子没有孩子，不影响关键字和孩子的关系。

分裂过程：

1. 找到关键字的中位数
2. 将中位数右边的关键字移动到新建的兄弟节点，注意：连同关键字的左右孩子一起移动。
3. 将中位数插入到父节点，没有父节点就创建父节点（根节点），将父节点新增关键字的左右指针指向左（分裂节点）右（新增的兄弟节点）孩子。父节点新增一个关键字和一个孩子（新增的兄弟节点）

为什么分支节点（根节点例外）的关键字最少是m/2-1？
因为分支节点都是分裂出来的，对于刚分裂的节点关键字是最少的，要将m/2移动到兄弟节点，还要将中位数移动到父节点，所以是m/2-1。

为什么根节点至少有两个孩子？
根节点也是分裂出来的（第一个叶节点例外），刚分裂出来的根节点有1个关键字，2两个孩子，所以根节点至少有两个孩子。根节点分裂，B树整体才会增加一层。

为什么要将中位数移动到父节点？
因为新增了一个兄弟节点（父节点的子节点），对于父节点（分支节点）增加1个孩子就要增加1个关键字。

B树是平衡树吗？
B树是天然平衡的，因为B树是向右和向上生长的：新增的关键字只能插入到叶子节点，叶节点满了分裂出一个兄弟节点，新增一个父节点关键字。父节点满了分裂出一个兄弟节点，新增一个根节点……

为什么要多开一个空间？
对于一棵m阶(m>2)的B树，一般申请m个关键字空间和m+1个孩子指针空间。多开一个空间就可以先插入再分裂。如果关键字<=m-1，表示节点满足性质，不分裂。如果关键字==m，表示节点满了，需要进行分裂。先插入再分裂方便计算中位数位置、移动后一半关键字等。如果不多开一个空间，就需要进行复杂的计算得到新插入关键字的位置、中位数的位置等。

---

三、B树的插入分析

为了简单起见，假设M = 3. 即三叉树，每个节点中存储两个数据，两个数据可以将区间分割成三个部分，因此节点应该有三个孩子，为了后续实现简单，数据域和指针域分别多开一个空间，节点的结构如下：

注意：孩子永远比关键字多一个

用序列{53, 139, 75, 49, 145, 36, 101}构建B树的过程如下：

1. 如果树为空，直接插入新节点中，该节点为树的根节点
2. 树非空，找待插入元素在树中的插入位置(注意：找到的插入节点位置一定在叶子节点中)
3. 按照插入排序的思想将该元素插入到找到的节点中

---

3. 检测该节点是否满足B-树的性质：即该节点中的元素个数是否等于M，如果小于则满足

4. 如果插入后节点不满足B树的性质，需要对该节点进行分裂：

   1. 申请新节点

   2. 找到该节点的中间位置

   3. 将该节点中间位置右侧的元素及其左右孩子搬移到新节点中

   4. 将中间位置元素插入到父节点中，没有父节点就创建父节点（根节点），将父节点新增关键字的左右指针指向左（分裂节点）右（新增的兄弟节点）孩子。

---

---

---

插入过程总结：

1. 如果树为空，直接插入新节点中，该节点为树的根节点
2. 树非空，找待插入元素在树中的插入位置(注意：找到的插入节点位置一定在叶子节点中)
3. 检测是否找到插入位置(假设树中的key唯一，即该元素已经存在时则不插入)
4. 按照插入排序的思想将该元素插入到找到的节点中
5. 检测该节点是否满足B-树的性质：即该节点中的元素个数是否等于M，如果小于则满足
6. 如果插入后节点不满足B树的性质，需要对该节点进行分裂：
   1. 申请新节点
   2. 找到该节点的中间位置
   3. 将该节点中间位置右侧的元素及其左右孩子搬移到新节点中
   4. 将中间位置元素及新节点指针往该节点的父节点中插入，重复步骤4
7. 如果节点满足B树的性质，或是向上已经分裂到根节点的位置，插入结束

---

四、B树的实现

4.1 B树的节点设计

template <class K, size_t M> //K是关键字类型，M是B树的阶数
struct BTreeNode{
    // 为了方便先插入后分裂，多开一个空间
    int _keys[M]; //M阶的B树节点中有M-1个关键字 +1
    BTreeNode* _subs[M+1]; //M阶的B树节点中有M个孩子 +1
    BTreeNode* _parent;
    int _n; //节点中存储key的个数
    
    BTreeNode()
    {
        for(int i = 0; i < M; ++i)
        {
            _keys[i] = K();
            _subs[i] = nullptr;
        }
        _subs[M] = nullptr;
        _n = 0;
        _parent = nullptr;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

4.2 B树的查找

template <class K, size_t M>
class BTree{
    typedef BTreeNode<K, M> Node;
    Node* _root;

public:
    BTree()
    :_root(nullptr)
    {}

    std::pair<Node*, int> find(const K& key)
    {
        Node* cur = _root;
        Node* parent = nullptr;
        while(cur)
        {
            //在一个节点中查找
            int i = 0;
            for(; i < cur->_n; ++i)
            {
                if(key < cur->_keys[i])
                {
                    break;
                }
                else if(key == cur->_keys[i])
                {
                    return std::make_pair(cur, i);
                }
            }
            parent = cur;
            cur = cur->_subs[i];
        }
        return std::make_pair(parent, -1); //找不到返回要插入的叶子节点和-1
    }
    //......
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

---

4.3 B树的插入

template <class K, size_t M>
class BTree{
    typedef BTreeNode<K, M> Node;
    Node* _root;

public:
    //......
    bool insert(const K& key)
    {
        if(_root == nullptr)
        {
            _root = new Node;
            _root->_keys[0] = key;
            _root->_n++;
            return true;
        }

        std::pair<Node*, int> ret = find(key);
        if(ret.second != -1)
        return false; //key已经存在不允许插入
        Node* cur = ret.first;
        insert_node(cur, key, nullptr); //将关键字插入到叶子节点

        //检查是否需要进行分裂，cur==nullptr表示上一次是根节点分裂,循环结束
        while(cur != nullptr && cur->_n == M) 
        {
            Node* parent = cur->_parent;
            Node* brother = new Node;
            int midi = cur->_n/2;
            int i = midi+1, j = 0;
            
            //将中位数右侧的元素搬移到新建的兄弟节点
            for(; i < cur->_n; ++i, ++j) 
            {
                //拷贝key和他的孩子
                brother->_keys[j] = cur->_keys[i];
                brother->_subs[j] = cur->_subs[i];
                if(cur->_subs[i] != nullptr) //注意要修改孩子的父节点指针
                {
                    cur->_subs[i]->_parent = brother;
                }
                cur->_keys[i] = K(); //# 为方便调试将搬移后的数据清零
                cur->_subs[i] = nullptr; //# 实际可以不写
            }
            brother->_subs[j] = cur->_subs[i]; //最后一个右孩子也要拷走
            if(cur->_subs[i] != nullptr)
            {
                cur->_subs[i]->_parent = brother;
            }
            cur->_subs[i] = nullptr; //#
            brother->_n = j;
			
            //将中位数和brother插入到父节点，没有父节点创建父节点（根节点）
            if(parent == nullptr) //cur是根节点
            {
                _root = new Node;
                _root->_keys[0] = cur->_keys[midi];
                _root->_subs[0] = cur;
                _root->_subs[1] = brother;
                _root->_n = 1;
                cur->_parent = _root;
                brother->_parent = _root;
            }
            else 
            {
                insert_node(parent, cur->_keys[midi], brother); //将中位数和brother插入到父节点
                brother->_parent = parent; 
            }
            cur->_keys[midi] = K(); //#
            cur->_n -= (brother->_n+1); //记得修改cur节点的关键字个数
            
            cur = parent; //继续向上检查parent是否需要进行分裂
        }
        return true;
    }
    
private:
    bool insert_node(Node* cur, const K& key, Node* child)
    {
        int end = cur->_n-1;
        while(end >= 0)
        {
            if(cur->_keys[end] > key)
            {
                //挪动key和他的右孩子
                cur->_keys[end+1] = cur->_keys[end];
                cur->_subs[end+2] = cur->_subs[end+1];
                --end;
            }
            else
            {
                break;
            }
        }
        cur->_keys[end+1] = key; //两种情况：1.end移动到-1位置 2.key>=[end]
        cur->_subs[end+2] = child;
        cur->_n++;
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

---

4.4 B树的中序遍历

template <class K, size_t M>
class BTree{
    typedef BTreeNode<K, M> Node;
    Node* _root;

public:
    //......
    void inorder()
    {
        _inorder(_root);
        std::cout << std::endl;
    }
    
private:
    //......
    void _inorder(const Node* cur)
    {
        int i = 0;
        for(; i < cur->_n; ++i)
        {
            if(cur->_subs[i] != nullptr)
            {
                _inorder(cur->_subs[i]);
            }
            std::cout << cur->_keys[i] << " ";
        }
        
        if(cur->_subs[i] != nullptr)
        {
            _inorder(cur->_subs[i]);
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

---

4.5 B树的删除（了解）

B树的关键字删除是指在一个B树数据结构中删除一个特定的关键字。当删除一个关键字时，需要保持B树的平衡和性质。

B树的关键字删除操作可以分为以下步骤：

1. 在B树中搜索需要删除的关键字：

   • 从根节点开始，按照B树的搜索规则向下遍历节点，找到包含要删除关键字的节点。
   • 如果找到了要删除的关键字，则执行删除操作；否则，说明要删除的关键字不存在。

2. 如果要删除的关键字在一个非叶子节点上（内部节点）：

   • 找到该关键字的前驱（左）或后继（右）关键字（通常选择前驱节点的最大或后继节点的最小关键字）进行替换。
   • 递归地删除替换的关键字。

3. 如果要删除的关键字在一个叶子节点上：

   • 直接删除该关键字并调整叶子节点的结构。
   • 如果删除后导致节点的关键字个数小于下限，则需要进行一些操作来保持B树的平衡。

4. 在删除关键字后可能需要进行的调整操作包括：

   • 合并节点：如果删除操作导致节点关键字个数小于下限，合并节点至邻近节点。
   • 重新分配：如果删除操作导致节点的关键字个数小于下限，但兄弟节点的关键字个数仍在合理范围内，则将部分关键字进行重新分配。
   • 递归删除：如果进行了合并或重新分配，则可能会涉及到对包含被删除关键字的父节点进行相同的操作。

这些步骤涵盖了B树关键字删除操作的基本过程，具体实现时需要根据B树的具体实现方式和性质进行调整和优化。

---

4.6 B树的性能分析

对于一棵节点为N，度为M的B树，查找和插入需要最少log{M}N次 ~ 最多log{M/2}N + 1次比较（M/2向上取整）：

• 对于度为M的B树，每一个分支节点的子节点个数为M ~ M/2之间，
• 在全满情况下：通过等比数列求和，树的高度最小为 log{M}N；
• 在全半满情况下（除根以外，根节点至少2个子节点）：通过等比数列求和，树的高度最大为log{M/2}N+1。
• 在定位到该节点后，再采用二分查找的方式可以很快的定位到该元素，在M个元素中进行二分查找，复杂度可以忽略不计。

B-树的效率是很高的，对于N = 62*1000000000个节点，如果度M为1024，则最坏情况下（全半满）树的高度为 log_{M/2}N+1=5。即在620亿个元素中，如果这棵树的度为1024，则需要小于5次即可定位到该节点，然后利用二分查找可以快速定位到该元素，大大减少了读取磁盘的次数。

---

五、B+树和B*树

5.1 B+树

5.1 B+树
B+树是B树的变形，是在B树基础上优化的多路平衡搜索树，B+树的规则跟B树基本类似，但是又在B树的基础上做了以下几点改进优化：

1. 分支节点的子树指针与关键字个数相同

2. 分支节点的子树指针p[i]指向关键字值大小在[k[i]，k[i+1])区间之间。分支节点中的关键字其实是对应子树中的最小值。

3. 所有叶子节点增加一个链接指针链接在一起，方便进行遍历

4. 分支节点只用于建立索引因此只有部分关键字的拷贝不存放映射地址，所有关键字(key)及其映射数据(磁盘地址)都存储在叶子节点

B+树的特性：

1. 所有关键字都出现在叶子节点的链表中，且链表中的节点都是有序的，方便进行遍历。
2. 不可能在分支节点中命中。
3. 分支节点相当于是叶子节点的索引，叶子节点才是存储数据的数据层。
4. 在B树中，不管是分支节点还是叶子节点，既要存储key又要存储映射地址，单个节点体量较大。而在B+树中，分支节点只用于建立索引因此只有部分关键字的拷贝，所有关键字及其映射地址都存储在叶子节点，单个节点体量较小。面对海量数据时，分支节点体量小就可以尽可能多的缓存到cache，从而减少磁盘I/O次数。（理论上，分支节点应该尽可能多的缓存到cache）

---

B+树的插入演示

将{53, 139, 75, 49, 145, 36, 101, 150, 155}依次插入到M=3的B+树中：

B+树的插入过程跟B树基本类似，区别1在于：第一次插入两层节点一层做分支用于索引，一层做叶子用于存储数据

---

区别2在于：叶节点满，分裂一半给新建的兄弟节点（不必再找中位数），再向父节点插入一个key和一个孩子：key是brother中的最小值在，孩子指向brother。父节点用于索引不存储数据，因此key是拷贝不是移动

---

---

---

区别3：根节点分裂，将一半分给新建的兄弟节点（不必再找中位数），再新建一个父节点（根节点）将两节点的最小值和指针拷贝到父节点

---

5.2 B*树

B*树在B+树的基础上又做了几点变形：

1. 分裂策略有所改进：分支节点的关键字个数下限变为了2/3M，空间利用率更高
2. 在分支节点（非根）中也加入了指向兄弟节点的指针，方便后续的分裂过程。

对比B+树的分裂：
当一个结点满时，分配一个新的结点，并将原结点中1/2的数据移动到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针。

B*树的分裂：
当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；
如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各移动1/3的数据到新结点，最后在父结点增加新结点的指针。
因此，B*树分配新结点的概率比B+树要低，空间使用率更高；

---

六、总结

通过以上介绍，大致将B树，B+树，B*树总结如下

• B树：有序数组+平衡多叉树；
• B+树：有序数组链表+平衡多叉树；
• B*树：一棵更丰满的，空间利用率更高的B+树

B树适用于外查找

B树（系列）是一种适合外查找的树，他通过提高节点度数、增加关键字个数，来压缩高度、减少查找次数，从而达到减少磁盘I/O操作的目的

为什么不用B树做内查找？

1. B 树的节点通常比较大，占用更多的内存空间，且关键字个数下限为M/2，空间利用率低（磁盘的存储空间很大，可以接受）
2. 在B树中为了保持平衡，插入和删除数据时可能需要进行频繁的节点分裂和合并操作，其中必然涉及数据的挪动和拷贝，这些操作可能会导致性能下降。
3. 虽然B树的高度更低，查找的时间复杂度降到了 log{M}N，但对于内存的访存速度而言，跟哈希和平衡搜索树log{2}N还是一个量级的（磁盘的读写速度很慢，log{M}N和log{2}N的差别巨大）

---

七、B树的应用

7.1 索引

B-树最常见的应用就是用来做索引。索引通俗的说就是为了方便用户快速找到所寻之物，比如：书籍目录可以让读者快速找到相关信息，hao123网页导航网站，为了让用户能够快速的找到有价值的分类网站，本质上就是互联网页面中的索引结构。

MySQL官方对索引的定义为：索引(index)是帮助MySQL高效获取数据的数据结构，简单来说：索引就是数据结构。

当数据量很大时，为了能够方便管理数据，提高数据查询的效率，一般都会选择将数据保存到数据库，因此数据库不仅仅是帮助用户管理数据，而且数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用数据，这样就可以在这些数据结构上实现高级查找算法，该数据结构就是索引

---

7.2 MySQL索引简介

mysql是目前非常流行的开源关系型数据库，不仅是免费的，可靠性高，速度也比较快，而且拥有灵活的插件式存储引擎，如下

MySQL中索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的。

注意：索引是基于表的，而不是基于数据库的。

---

7.2.1 MyISAM

MyISAM引擎是MySQL5.5.8版本之前默认的存储引擎，不支持事物，支持全文检索，使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址，其结构如下：

上图是以以Col1为主键，MyISAM的示意图，可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果想在Col2上建立一个辅助索引，则此索引的结构如下图所示：

同样也是一棵B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。MyISAM的索引方式也叫做“非聚集索引”的。

---

7.2.2 InnoDB

InnoDB存储引擎支持事务，其设计目标主要面向在线事务处理的应用，从MySQL数据库5.5.8版本开始，InnoDB存储引擎是默认的存储引擎。InnoDB支持B+树索引、全文索引、哈希索引。但InnoDB使用B+Tree作为索引结构时，具体实现方式却与MyISAM截然不同。

第一个区别是InnoDB的数据文件本身就是索引文件。MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而InnoDB索引，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

上图是InnoDB主索引（同时也是数据文件）的示意图，可以看到叶节点包含了完整的数据记录，这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整型。

第二个区别是InnoDB的辅助索引data域存储相应记录主键的值而不是地址,所有辅助索引都引用主键作为data域。

聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。