前言

一.B树概念

1.1 概念和性质

1.2 分裂

二.插入的实现

三.性能分析

四.B树的删除

五.B树的优化B+树和B*树

5.1 B+树

5.2 B*树

六.B树的应用

6.1 MyISAM中的索引

6.2 Innodb引擎

前言

之前我们学了有很多数据结构，比如顺序表，链表，栈，队列和二叉树。也有很多高效的数据结构。比如：二叉搜索树，平衡二叉树，红黑树和哈希表等。但是，这些数据结构只适用于数据量不大的情况。

如果数据量很大，一次性无法加载到内存中。数据需要保存在磁盘中。

在磁盘中如果用以上的数据结构组织，效率同样会很低。比如：在磁盘中，用红黑树组织数据。会有以下的缺陷：

树的高度比较高，查找最差的情况需要比较高度次。
数据量比较大时，不能将所有结点读取到内存中，需要进行多次IO。

如何提高对数据的访问呢？

降低树的高度。
减少IO次数。

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

说明：大量数据时，是在磁盘中组织成B树的结构。再将B树结点(保存数据)读取到内存中。并不是将数据读取到内存中，再组织成B树的结构。

一.B树概念

1.1 概念和性质

B树是一颗多叉平衡树，一颗M(M>2)阶的B树。可以是空树或者满足以下性质。

根节点至少有两个孩子结点。
每一个非根结点至少有M/2(向上取整)个孩子结点，至多有M个孩子结点。
非根结点，至少M/2-1(向上取整)个关键字，至多有M-1个关键字，并且以升序排列。
key[i] 和key[i+1]之间的孩子结点值介于key[i]和key[i+1]值之间。(保证是搜索树)。
所有叶子结点在同一层。

总结以下：

关键字的数量比孩子结点数少1。
根节点关键字数量范围[1，M-1]，孩子结点数量[2，M]。
非根节点关键字数量范围[M/2-1，M-1]，孩子数量[M/2，M]。
每一个节点关键字在节点中以升序排列。
所有叶子节点都在同一层。

B树的高度低是：因为每一个节点的会保存多个数据，并且是多叉树。

1.2 分裂

根据B树的性质，当插入数据，节点的数据个数到达M个时(超过上限)，需要进行分裂。

分裂：分裂出一个兄弟节点，分出一半的关键字给兄弟节点。中位数插入父节点。如果父节点不存在，创建一个父节点，再插入。

细节：兄弟节点不仅要拷贝关键字，还需要将对应孩子节点拷贝。

下面画图来演示一下：

为了简单起见，假设M=3，即三叉树。由上面B树的性质，可以知道，每一个节点中最多保存2个关键字，有3个孩子节点。

但是，我们设计成可以存储3个关键字，4个孩子节点。

原因是：如果关键字个数等于M-1时，来了一个值，我们需要先插入，排好序，才方便确定分出的一半关键字。

注意：孩子节点比关键字多一个。

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

二.插入的实现

过程：

B树中没有节点，创建节点后，直接插入。
插入的节点，必须插入到叶子节点中。所以首先需要找到叶子节点。
插入节点存在，不插入。
插入节点不存在，按照插入排序法，插入节点。
插入节点后的情况：
1. 插入节点没有破坏B树性质(数据个数超过M-1)，不需要操作。
2. 插入节点破坏B树的性质，进行分裂。创建兄弟节点，拷贝一半数据和对应孩子节点，如果没有根节点，创建根节点，中间数据和对应孩子节点直接插入。
3. 插入节点破坏B树的性质，进行分裂。创建兄弟节点，拷贝一半数据和对应孩子节点，如果有父节点，中间数据和对应孩子节点插入到对应位置。如果父节点B树性质被破坏，需要将父节点重复分裂操作操作。直到父节点没有破坏B树性质。

为什么必须往叶子节点插入？

如果不往叶子节点插入，插入一个数据，还需要一个孩子节点，并且不为空。

往叶子节点插入，插入一个数据，孩子节点就是空。

分裂节点步骤：

找到当前节点的中间位置。
将中间位置右边数据拷贝到兄弟节点
将中间位置数据，插入到父节点中。
- 父节点不存在，创建父节点插入
- 父节点存在，按照插入排序插入，判断父节点否B树性质是否被破坏。破坏重复父节点分裂操作。
注意：孩子节点需要拷贝到对应位置。

节点设计：

数据个数最多M-1，孩子节点最多M个。设计多一个位置，当数据达到M-1时，需要插入节点时，方便先插入，再选择需要搬走的数据。

注意：孩子节点，数据左孩子节点的下标等于数据的下标，右孩子节点的下标等于数据下标加1。

template<class K, class V, size_t M>
struct BtreeNode{BtreeNode():parent(nullptr),ksize(0){for (int i = 0; i < M + 1; i++){child[i] = nullptr;}}//设计多一个位置，方便最后插入pair<K, V> k[M];//父子节点BtreeNode *child[M + 1];BtreeNode *parent;size_t ksize;
};

插入：

#pragma once
#include<iostream>
using namespace std;template<class K, class V, size_t M>
struct BtreeNode{BtreeNode():parent(nullptr),ksize(0){for (int i = 0; i < M + 1; i++){child[i] = nullptr;}}//设计多一个位置，方便最后插入pair<K, V> kv[M];//父子节点BtreeNode<K, V, M> *child[M + 1];BtreeNode<K, V, M> *parent;size_t ksize;
};template<class K, class V, size_t M>
class Btree{typedef BtreeNode<K, V, M> Node;
private:Node *root = nullptr;void InserKV(Node *cur, pair<K, V> kv, Node *sub){int i = cur->ksize - 1;while (i >= 0){if (cur->kv[i].first <= kv.first){break;}cur->kv[i + 1] = cur->kv[i];cur->child[i + 2] = cur->child[i + 1];i--;}cur->kv[i + 1] = kv;cur->child[i + 2] = sub;cur->ksize++;//注意更新父亲if (sub){sub->parent = cur;}}void _Inorder(Node *root){if (root == nullptr){return;}size_t i = 0;for (; i < root->ksize; i++){//先访问左_Inorder(root->child[i]);cout << root->kv[i].first<<" ";}//再访问最后一个右_Inorder(root->child[i]);}public://左孩子等于数据下标等于i//右孩子是数据下标是i+1pair<Node*, int> find(const K& key){Node *cur = root;Node *parent = nullptr;while (cur){parent = cur;size_t i = 0;while (i<cur->ksize){if (cur->kv[i].first < key){i++;}else if (cur->kv[i].first > key){break;}else{//找到return make_pair(cur, i);}}//cur = cur->child[i];}//没找到,返回上一个节点return make_pair(parent, -1);}bool Insert(const pair<K, V>& kv){if (root == nullptr){root = new Node;root->kv[0] = kv;root->ksize = 1;return true;}pair<Node *, int> ret = find(kv.first);if (ret.second >= 0){cout << "已存在" << endl;return false;}//插入，不存在Node *cur = ret.first;//插入的节点pair<K, V> newkv = kv;//插入的KVNode *sub = nullptr;//插入的孩子节点//往cur插入sub和newkvwhile (1){InserKV(cur, newkv, sub);if (cur->ksize < M){return true;}//需要分裂//兄弟节点Node *bro = new Node;//拷贝一半的数据size_t mid = M / 2;size_t j = 0;size_t i = mid + 1;for (; i < cur->ksize; i++){bro->ksize++;bro->kv[j] = cur->kv[i];//还需要将子节点拷贝过去bro->child[j] = cur->child[i];cur->child[i] = nullptr;cur->kv[i] = pair<K, V>();//注意更新父亲节点if (bro->child[j]){bro->child[j]->parent = bro;}j++;}//还剩最后一个孩子bro->child[j] = cur->child[i];cur->child[i] = nullptr;if (bro->child[j]){bro->child[j]->parent = bro;}cur->ksize = mid;//1.没有父亲，cur就是根，产生新根//2.有父亲，插入数据和孩子,继续判断是否需要分裂if (cur->parent == nullptr){//没有父节点//创建新根root = new Node;root->kv[0] = cur->kv[mid];root->ksize = 1;cur->kv[mid] = pair<K, V>();//更新父节点和子节点root->child[0] = cur;root->child[1] = bro;cur->parent = root;bro->parent = root;return true;}//有父节点,插入bro和kv[mid]利用循环 newkv = cur->kv[mid];cur->kv[mid] = pair<K, V>();cur = cur->parent;sub = bro;}}//中序遍历void Inoeder(){_Inorder(root);}};

三.性能分析

对于一颗节点为N度为M的B树，查找和插入的时间在以M-1为底LogN到以M/2为底的LogN之间。因为一个节点的数据在[M/2，M-1]之间。

定位到节点后，由于数据保存是有序的。可以利用二分查找查找，查找该数据。这样效率是很高的。

并且对于数据量很多的情况，树的高度也会很低。因为一个节点的保存的数据M是可以控制的，并且它是多叉树。

比如：如果M设置为1024。

B树第一层：保存的数据最多1023

B树第二层：保存的数据最多1024*1023

B树第三层：保存的数据最多1024*1024*1023

B树底四层：保存的数据最多1024*1024*1024*1023

......

当N=62*1000000000个数据，最多只需要4次就可以定位到元素。

如何实现IO次数少的？

在磁盘中按照B树的结构保存数据。在查找数据时，假设：每次读一个节点上来。根据数据的大小，找到孩子节点。再将孩子节点读上来。IO的最大次数是B树的高度次。由于B树高度低。所以IO次数少。

B树没有经过平衡调节，是如何达到平衡的？

B树只有在节点满的时候，才会新增一层。但是是从下往上增长的。并且分裂多了一个节点是从左往右增长的。B树天然就会是平衡的。

B树的的所有叶子节点在同一层，近似于完全二叉树的结构。

四.B树的删除

简单思路：

如果是叶子节点，可以直接删除。

不是叶子节点，到左孩子中拿最大值或者在右孩子中拿最小值上来。如果被借值的节点不是叶子节点，需要继续往下借，直到借到叶子节点。

因为：如果删除一个数据，就需要删除一个系欸但，只有叶子节点的孩子节点为空，方便删除。

如果叶子节点删完后值得数量不够1了，找同层的兄弟节点借。

如果兄弟节点也借完之后也会值的数量也不够1，就将两个节点合并。

五.B树的优化B+树和B*树

5.1 B+树

B+树是B树的变形，也是一颗多路搜索树。

定义和B树基本相同。
非叶子节点的子树指针与关键字数量相同。
非叶子节点的子树关键字值sub[i]在当前关键字[k[i]，k[i+1])之间。(保证搜索树的性质)。
所有叶子节点增加一个链指针，将所有叶子节点连接起来。
所有数据都保存在叶子节点中。

总结：

根节点关键字和孩子数量为[1，M]个。
非根节点关键字和孩子的数量为[M/2，M]个。
每个节点中关键字的数量等于孩子数量。
节点中的数据，按照升序排列，并且，孩子节点的值sub[i]在当前节点k[i]和k[i+1]之间。
所有数据保存在叶子节点中，非叶子节点值保存了关键字。父亲节点只保存了当前节点中关键字最小的。
所有叶子节点都连接起来，还有一个指针指向第一个叶子节点。

如下图：

B+树的特性：

所有数据都保存在叶子节点的链表中(稠密索引)，且链表的结点是有序的。
数据不可能在非叶子结点命中。
非叶子结点相当于叶子结点的索引。如果是KV模型，非叶子结点中只保存K，并且是孩子结点中最小的。

用在文件系统中，非叶子结点相当于数据索引，叶子节点相当于存储数据的数据层。

B+树和B树的区别：

B+树只能在叶子节点命中数据(数据保存在叶子节点中)，B树可以在非叶子节点命中数据。

B+树节点关键字数量和孩子数量相同。B树孩子数量比关键字数量少一个。

B+树的优点：

方便遍历，所有值保存在叶子节点中，并且用链表连接起来了。

B+树的插入：

如果B+树为空，创建父亲节点和叶子节点，数据保存在叶子节点中，根节点，保存关键字。
如果B+树不为空，找到叶子节点插入。
如果插入节点是最小值，更新父节点中保存的数据。
如果叶子节点插入满了，需要进行分裂。

分裂和B树分裂差不多。

创建兄弟节点，拷贝一半数据给兄弟节点。
将兄弟节点的最小关键字插入到父亲节点中。
判断父亲节点是否满了。
满了父亲节点分裂，重复上面动作。

5.2 B*树

B*树是在B+树的基础上，做了优化。有人觉得B+树在分裂时，是分配一半的数据给兄弟节点，如果一种不往节点插入数据，就会导致节点中空间浪费了1/2。

B*树，增加了空间利用率。从1/2提高到了2/3。

B*树是B+树的变形，在B+树的非根和非叶子节点再增加指向兄弟节点的指针。

B*树的分裂：

不会直接生成新节点。如果兄弟节点中有空间，会将部分数据插入到兄弟节点中，再将数据插入到原节点。

如果兄弟节点也满了，再创建新节点，将原节点1/3的数据插入新节点中，将兄弟节点1/3的数据插入新节点中。

再按照B+树的规制，将新节点的最小关键字，插入到父亲节点中，并且更新孩子节点指针。

所以B*树空间利用率会高于B+树。

六.B树的应用

B树最常见的应用主要是用来做索引。索引是一种基于B树数据结构，主要应用在数据库中。

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

下面讨论主流的数据库MySQL。

MySQL中索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的。MySQL最常用的两种存储引擎是MyISAM和Innodb。

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

6.1 MyISAM中的索引

MyISAM引擎是MySQL5.5.8版本以前的存储引擎。不支持事务，支持全文检索，使用B+树作为索引结构。用叶节点保存数据的地址或者相对路径。

B+树非叶子节点保存的数据是主键值，主键值在MySQL中是唯一的。叶子节点中保存了树的路径。

通过主键值来查找数据保存的路径，效率很高，O(以M为底的LogN~以M/2为底的LogN)。

但是如果查找数据不是通过主键值，就只能通过遍历叶子节点来查找数据(B+树将叶子节点被组织成了链表结构)，效率很低O(N)。

上面是以Col1为主键构成的索引结构。

假如：一个值不是主键，因为可以重复，但是我们会经常使用这个值来查找数据，效率很低怎么办？

我们可以以这个值来建立辅助索引数据结构，同样，辅助索引也是一颗B+树。只是辅助索引节点保存的关键字可以重复。

MyISAM引擎节点中保存的是数据的地址或者路径，在通过路径来找到数据。这种索引方式叫做"非聚集索引"。

主索引是以主键创建的索引数据结构，节点保存的关键字不能重复。
辅助索引不是以主键创建的索引数据结构，节点保存的关键字可以重复。

6.2 Innodb引擎

Innodb是从MySQL5.58版本开始的，支持事务，支持B+树索引，全文索引，哈希索引。可以算是MyISAM的优化版本。

但是InnoDB引擎使用B+树作为索引数据结构，实现方式和MyISAM截然不同。

区别一：

Innodb数据文件本身就是索引文件，意思就是，索引结构的叶节点中直接保存着数据，这种索引叫做"聚集索引"。而MyISAM索引文件和数据文件分离，索引结构中只是保存数据的路径，再通过路径找数据。

区别二：

Innodb要求表中必须有主键，因为Innodb索引文件(数据文件)，本身要按主键来构建索引结构。如果用户没有显示设置主键，MySQL会自动选择一个可以唯一标识数据记录的列作为主键，比如：自增字段。如果不存在这种列，MySQL会为Innodb表自动生成一个隐含字段作为主键。这个字段占6字节，类型为长整型。

MyISAM可以没有主键。

以主键构建的索引为主索引。