[C++][数据结构][B-树][下]详细讲解

1.B-树的实现
- 1.B-树的结点设计
- 2.插入key的过程
- 3.B-树的插入实现
- 4.B-树的简单验证
- 5.B-树的性能分析
- 6.B树的删除
2.B+树
3.B*树
4.B-树总结
5.B-树的应用
- 0.B树可以在内存中做内查找吗？
- 1.索引
- 2.MYSQL索引简介
- - 1.MyISAM
  - 2.InnoDB
- 3.B+树做主键索引相比B树的优势

1.B-树的实现

1.B-树的结点设计

template<class K, size_t M>
struct BTreeNode
{
	// 为了方便插入以后再分裂，多给一个空间
	K _keys[M];
	BTreeNode<K, M>* _subs[M + 1];     

	BTreeNode<K, M>* _parent = nullptr;;
	size_t _n = 0; // 记录实际存储关键字的个数

	BTreeNode()
	{
		for (size_t i = 0; i < M; i++)
		{
			_keys[i] = K();
			_subs[i] = nullptr;
		}

		_subs[M] = nullptr;
	}
};

2.插入key的过程

按照插入排序的思想插入key
- 注意：在插入key的同时，可能还要插入新分裂出来的节点

void InsertKey(Node* node, const K& key, Node* child)
{
	// 直接插入排序
	int end = node->_n - 1;

	while (end >= 0)
	{
		if (key < node->_keys[end])
		{
			node->_keys[end + 1] = node->_keys[end];
			node->_subs[end + 2] = node->_subs[end + 1];
			end--;
		}
		else
		{
			break;
		}
	}

	node->_keys[end + 1] = key;
	node->_subs[end + 2] = child; // 该结点的右子树
	if (child)
	{
		child->_parent = node;
	}

	node++;
}

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)
	{
		InsertKey(parent, newKey, child);

		// 没有满，插入就结束
		if (parent->_n < M)
		{
			return true;
		}
		
		// 满了就要分裂
		// 分裂一般[mid + 1, M - 1]给兄弟
		Node* bro = new Node;
		size_t mid = M / 2;
		size_t i = mid + 1;
		size_t j = 0;
		
		for (; i < M; i++)
		{
			// 分裂拷贝key和key的左孩子
			bro->_keys[j] = parent->_keys[i];
			bro->_subs[j++] = parent->_subs[i];
			
			// 更新parent->_keys[i]父节点为bro
			if (parent->_keys[i])
			{
				parent->_keys[i]->_parent = bro;
			}

			// 拷走之后，重置为默认值，方便观察
			parent->_keys[i] = K();
			parent->_subs[i] = nullptr;
		}

		// 还有最后一个最右孩子
		bro->_subs[j] = parent->_subs[i];
		if (parent->_keys[i])
		{
			parent->_keys[i]->_parent = bro;
		}
		parent->_subs[i] = nullptr;

		bro->_n = j;
		parent->_n -= (bro->_n + 1);

		K midkey = parent->_keys[mid];
		parent->_keys = K();

		// 说明刚刚分裂的是根节点
		if (parent->_parent == nullptr)
		{
			_root = new Node;
			_root->_keys[0] = midkey;
			_root->_subs[0] = parent;
			_root->_subs[1] - bro;
			_root->_n = 1;

			parent->_parent = _root;
			bro->_parent = _root;
			break;
		}
		else
		{
			// 转换成往parent->_parent中去插入midKey和bro
			newKey = midkey;
			child = bro;
			parent = parent->_parent;
		}
	}

	return true;
}

4.B-树的简单验证

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

	void _InOrder(Node* cur)
	{
		if (cur == nullptr)
		{
			return;
		}

		// 左 根 左 根 ... 右
		for (size_t i = 0; i < M; i++)
		{
			_InOrder(cur->_subs[i]); // 左子树
			cout << cur->_keys[i] << " "; // 根
		}
		_InOrder(cur->_subs[i]); // 最右子树
	}

	void InOrder()
	{
		_InOrder(_root);
	}

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 = 620亿个节点，如果度M为1024，则 $log_{(M/2)}N$ <= 4
- 即：在620亿个元素中，如果这棵树的度为1024，则需要小于4次即可定位到该节点，然后利用二分查找可以快速定位到该元素，大大减少了读取磁盘的次数

6.B树的删除

学习B树的插入足够帮助理解B树的特性了
大致思路：
- 节点数量小于 $m /2 - 1$ ，则优先找父亲借，父亲找兄弟借
- 若找父亲和兄弟借不到节点了，再借它们也不满足条件 $m /2 - 1$
  - 合并兄弟节点
若对删除有兴趣，可以参考参考
- 《算法导论》-- 伪代码
- 《数据结构-殷人昆》-- C++实现代码

2.B+树

B+树是B树的变形，是在B树基础上优化的多路平衡搜索树
B+树的规则跟B树基本类似，但又在B树的基础上做了以下几点改进优化：
- 分支结点的子树指针与关键字个数相同
  - 相当于取消了最左边的那个子树
- 分支结点的子树指针 $p [i]$ 指向关键字值大小在 $([k [i] ， k [i + 1])$ 区间之间
  - 分支结点跟叶子结点有重复的值，分支结点存的是叶子节点索引
  - 父亲中存的是孩子节点中的最小值的索引
- 所有叶子节点增加一个链接指针链接在一起
- 所有关键字及其映射数据都在叶子节点出现
B+树的特性：
- 所有关键字都出现在叶子节点的链表中，且链表中的节点都是有序的
- 不可能在分支结点中命中
- 分支节点相当于是叶子节点的索引，叶子节点才是存储数据的数据层
B+树的分裂：
- 第一次插入两层节点，一层做根，一层做分支
  - 后面跟B树一样，往叶子去插入
- 当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针
- B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针
B+ vs B
- 分支结点只存储key，分支结点比较小
- 分支结点映射的磁盘数据块就可以尽量加载到Cache
总结：
- 简化B树孩子比关键字多一个的规则，变成相等
- 所有值都在叶子上，方便遍历查找所有值

3.B*树

B*树是B+树的变形，在B+树的非根和非叶子节点再增加指向兄弟节点的指针
B*树的结点关键字和孩子数量 --> $[2/3 * M, M]$
B*树的分裂：当一个结点满时
- 如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了)
- 如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针
所以，B*树分配新结点的概率比B+树要低，空间使用率更高

请添加图片描述

4.B-树总结

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

5.B-树的应用

0.B树可以在内存中做内查找吗？

可以，但不合适
B树系列和哈希&平衡搜索树对比：
- 单纯轮树高度、搜索效率而言，B树确实不错
- 但是B树系列有一些隐形缺点：
  - 空间利用率低，消耗高
  - 插入删除数据时，分裂和合并节点，那么必然挪动数据
  - 虽然高度更低，都是在内存中而言，跟哈希和平衡搜索树还是一个量级
结论：实质上B树系列再内存中体现不出优势

1.索引

B-树最常见的应用就是用来做索引
索引通俗的说就是为了方便用户快速找到所寻之物，比如：
- 书籍目录可以让读者快速找到相关信息
- 网页导航网站，为了让用户能够快速的找到有价值的分类网站，本质上就是互联网页面中的索引结构
MySQL官方对索引的定义为：
- 索引(index)是帮助MySQL高效获取数据的数据结构
- 简单来说：索引就是数据结构
当数据量很大时，为了能够方便管理数据，提高数据查询的效率，一般都会选择将数据保存到数据库，因此数据库不仅仅是帮助用户管理数据，而且数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用数据，这样就可以在这些数据结构上实现高级查找算法，该数据结构就是索引

2.MYSQL索引简介

MySQL中索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的
注意：索引是基于表的，而不是基于数据库的

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的索引方式也叫做**“非聚集索引”**

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域
聚集索引这种实现方式使得按主键的搜索十分高效
- 但是辅助索引搜索需要检索两遍索引
  - 首先检索辅助索引获得主键
  - 然后用主键到主索引中检索获得记录