【高阶数据结构】 B树 -- 详解

1、使用平衡二叉树搜索树的缺陷

三、B-树 的插入分析

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

注意：孩子永远比数据多一个。

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

天然平衡，向右和向上生长，根节点分裂，增加一层。

新插入的节点一定是在叶子节点插入，叶子节点没有孩子，不影响关键字和孩子的关系。

叶子节点满了，分裂出一个兄弟，提取中位数，向父亲插入一个值和一个孩子。

插入过程总结：

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

四、B-树 的插入实现

1、B-树 的节点设计

// M叉树：即一个节点最多有M个孩子，M-1个数据域
template<class K, size_t M>
struct BTreeNode
{
	//K _keys[M - 1];
	//BTreeNode<K, M>* _subs[M];
 
	// 为了方便插入以后再分裂，多给一个空间
	K _keys[M]; // 存放元素
	BTreeNode<K, M>* _subs[M+1]; // 存放孩子节点，注意：孩子比数据多一个
	BTreeNode<K, M>* _parent;
	size_t _n; // 记录实际存储多个关键字 
 
	BTreeNode()
	{
		for (size_t i = 0; i < M; ++i)
		{
			_keys[i] = K();
			_subs[i] = nullptr;
		}
		_subs[M] = nullptr;
		_parent = nullptr;
		_n = 0;
	}
};

2、插入 key 的过程

按照插入排序的思想插入 key。

void InsertKey(Node* node, const K& key, Node* child)
{
	// 按照插入排序思想插入key
	int end = node->_n - 1;
	while (end >= 0)
	{
		if (key < node->_keys[end])
		{
			// 将key和他的右孩子往右搬移一个位置
			node->_keys[end + 1] = node->_keys[end];
			node->_subs[end + 2] = node->_subs[end + 1];
 			end--;
		}
		else
			break;
	}
	// 插入key以及新分裂出的节点
	node->_keys[end + 1] = key;
	node->_subs[end + 2] = child;
 
	// 更新节点的双亲
	if (child)
		child->_parent = node;
	node->_n++;
}

注意：在插入 key 的同时，可能还要插入新分裂出来的节点。

3、B-树 的插入实现

bool Insert(const K& key)
{
	// 如果树为空，直接插入
	if (_root == nullptr)
	{
		_root = new Node;
		_root->_keys[0] = key;
		_root->_n++;
		return true;
	}
 
	// key已经存在，不插入
	pair<Node*, int> ret = Find(key);
	if (ret.second >= 0)
	{
		return false;
	}
 
	// 如果没有找到，find顺便带回了要插入的那个叶子节点
	// 循环每次往cur插入newkey和child
	Node* parent = ret.first;
	K newKey = key;
	Node* child = nullptr;
	while (1)
	{
		// 将key插入到parent所指向的节点中
		InsertKey(parent, newKey, child);
		// 满了就要分裂；没有满，插入就结束
		if (parent->_n < M)
		{
			return true;
		}
		else
		{
			size_t mid = M / 2;
			// 分裂一半[mid+1, M-1]给兄弟
			Node* brother = new Node;
			// 将中间位置右侧的元素以及孩子搬移到新节点中
			size_t j = 0;
			size_t i = mid + 1;
			for (; i <= M - 1; i++)
			{
				// 分裂拷贝key和key的左孩子
				brother->_keys[j] = parent->_keys[i];
				brother->_subs[j] = parent->_subs[i];
				// 跟新孩子节点的双亲
				if (parent->_subs[i])
				{
					parent->_subs[i]->_parent = brother;
				}
				j++;
 
				// 拷走重置一下方便观察
				parent->_keys[i] = K();
				parent->_subs[i] = nullptr;
			}
 
			// 注意：还有最后一个右孩子拷给(孩子比关键字多搬移一个)
			brother->_subs[j] = parent->_subs[i];
		    if (parent->_subs[i])
			{
				parent->_subs[i]->_parent = brother;
			}
			parent->_subs[i] = nullptr;
 
			brother->_n = j;
			// 更新parent节点的剩余数据个数
			parent->_n -= (brother->_n + 1);
 
			K midKey = parent->_keys[mid];
			parent->_keys[mid] = K();
 
			// 如果刚刚分裂是根节点，需要重新申请一个新的根节点，
			// 将中间位置数据以及分裂出的新节点，插入到新的根节点中，插入结束
			if (parent->_parent == nullptr)
			{
				_root = new Node;
				_root->_keys[0] = midKey;
				_root->_subs[0] = parent;
				_root->_subs[1] = brother;
				_root->_n = 1;
				parent->_parent = _root;
				brother->_parent = _root;
				break;
			}
			else // 如果分裂的节点不是根节点，将中间位置数据以及新分裂出的节点继续向parent的双亲中进行插入
			{
				// 转换成往parent->parent去插入parent->[mid]和brother
				newKey = midKey;
				child = brother;
				parent = parent->_parent;
			}
		}
	}
	return true;
}

4、B-树 的简单验证

对 B树 进行中序遍历，如果能得到一个有序的序列，说明插入正确。

void _InOrder(Node* cur)
{
	if (cur == nullptr)
		return;
	// 左 根  左 根  ...  右
	size_t i = 0;
	for ( ; i < cur->_n; ++i)
	{
		_InOrder(cur->_subs[i]); // 左子树
		cout << cur->_keys[i] << " "; // 根
	}
	_InOrder(cur->_subs[i]); // 最后的那个右子树
}

---

5、B-树 的性能分析

对于一棵节点为 N 度为 M 的 B-树，查找和插入需要$log{M-1}N$~$log{M/2}N$次比较，这个很好证明：对于度为 M 的 B-树，每一个节点的子节点个数为 M/2 ~(M-1) 之间，因此树的高度应该在要 log(M-1)N 和 log(M/2)N 之间，在定位到该节点后，再采用二分查找的方式可以很快的定位

到该元素。

B-树 的效率是很高的，对于 N = 62*1000000000 个节点，如果度 M 为 1024，则 log(M/2)N <=

4，即在 620 亿个元素中，如果这棵树的度为 1024，则需要小于 4 次即可定位到该节点，然后利用 二分查找可以快速定位到该元素，大大减少了读取磁盘的次数。

---

五、B+树 & B*树

1、B+树

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

1. 分支节点的子树指针与关键字个数相同。
2. 分支节点的子树指针 p[i] 指向关键字值大小在 [k[i]，k[i+1]) 区间之间。
3. 所有叶子节点增加一个链接指针链接在一起。
4. 所有关键字及其映射数据都在叶子节点出现。

分支节点跟叶子节点有重复的值，分支节点村的是叶子节点的索引。

父亲中存的是孩子节点中的最小值做索引。

分支节点可以只存储 key，那么分支节点比较小，分支节点映射的磁盘数据块就可以尽快加载到 Cache。

叶子节点存 key/value。

---

（1）B+树 的特性

1. 所有关键字都出现在叶子节点的链表中，且链表中的节点都是有序的。
2. 不可能在分支节点中命中。
3. 分支节点相当于是叶子节点的索引，叶子节点才是存储数据的数据层。

B+树 的插入过程跟 B树 基本是类似的，细节区别在于：第一次插入两层节点，一层做分支，一层做根。

后面一样往叶子节点去插入，插入满了以后，分裂一半给兄弟，转换成往父亲插入一个 key 和一个孩子，孩子就是兄弟，key 是兄弟的第一个最小值得 key。

---

（2）总结

1. 简化 B树 孩子比关键字多一个的规则，变成相等。
2. 所有值都在叶子上，方便遍历查找所有值。

---

2、B*树

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

---

（1）B+树的分裂

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

---

（2）B*树的分裂

当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）。如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制 1/3 的数据到新结点，最后在父结点增加新结点的指针。

所以，B*树 分配新结点的概率比 B+树 要低，空间使用率更高。

---

3、总结

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

---

六、B-树 的应用

1、索引

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

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

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

B+树 做主键索引相比 B树 的优势：

1. B+树 所有的值都在其叶子节点上，遍历方便，方便区间查找。
2. 对于没有建立索引的字段，全表扫描的遍历很方便。
3. 分支节点只存储 key，一个分支节点的空间占用更小，可以尽可能加载到缓存中。

B树 的优势：不需要遍历到叶子节点就能找到值，而 B+树 一定要遍历到叶子节点。但是 B+树 的高度足够低，所以二者差别并不大。

---

2、MySQL 索引简介

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

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

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

---

（1）MyISAM

MyISAM 引擎是 MySQL 5.5.8 版本之前默认的存储引擎，不支持事务，支持全文检索，使用 B+Tree 作为索引结构，叶节点的 data 域存放的是数据记录的地址（方便索引树和主键树映射同样的数据），其结构如下：

建表的主键就是 B+树 的 key，B+树 的 value 事存储一行数据的磁盘地址。

分支节点也需要存到磁盘中，因为数据量大的话，内存是存不下的。分支节点中应该是一个磁盘地址，但是分支节点理论应该尽量被缓存到 Cache。

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

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

---

（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 建立索引时，索引树的叶子节点和主键树的叶子节点中的数据不一样，没有办法进行直接映射。

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

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

参考资料：【高阶数据结构】MySQL 索引背后的数据结构及算法原理-CSDN博客