数据结构:图解手撕B-树以及B树的优化和索引

这篇具有很好参考价值的文章主要介绍了数据结构:图解手撕B-树以及B树的优化和索引。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

本篇总结的内容是B-树

为什么需要引入B-树?

回忆一下前面的搜索结构,有哈希,红黑树,二分…等很多的搜索结构,而实际上这样的结构对于数据量不是很大的情况是比较适用的,但是假设有一组很大的数据,大到已经不能在内存中存储,此时应该如何处理呢?可以考虑将关键字及其映射的数据的地址放到一个内存中的搜索树的节点,优先考虑去这个地址处访问数据

数据结构:图解手撕B-树以及B树的优化和索引,C++,数据结构,知识总结,数据结构,b树
数据结构:图解手撕B-树以及B树的优化和索引,C++,数据结构,知识总结,数据结构,b树
从上面的文段中可以看出,问题出现在文件的IO是有损耗的,因此在使用哈希或是其他的数据结构,在搜索的过程中会不断地进行文件的IO,这样带来的降低效率是不建议出现的,因此解决方案之一就是可以降低树的高度,因此就引出了B-树:多叉平衡树

B树是什么?

1970年,R.BayerE.mccreight提出了一种适合外查找的树,它是一种平衡的多叉树,称为B树(后面有一个B的改进版本B+树,然后有些地方的B树写的的是B-树,一棵m阶(m>2)的B树,是一棵平衡的M路平衡搜索树,可以是空树或者满足一下性质:

  1. 根节点至少有两个孩子
  2. 每个分支节点都包含k-1个关键字和k个孩子,其中 ceil(m/2) ≤ k ≤ m ceil是向上取整函数
  3. 每个叶子节点都包含k-1个关键字,其中 ceil(m/2) ≤ k ≤ m
  4. 所有的叶子节点都在同一层
  5. 每个节点中的关键字从小到大排列,节点当中k-1个元素正好是k个孩子包含的元素的值域划分
  6. 每个结点的结构为:(n,A0,K1,A1,K2,A2,… ,Kn,An)其中,Ki(1≤i≤n)为关键字,且Ki<Ki+1(1≤i≤n-1)Ai(0≤i≤n)为指向子树根结点的指针。且Ai所指子树所有结点中的关键字均小于Ki+1n为结点中关键字的个数,满足ceil(m/2)-1≤n≤m-1

上面的规则很复杂,那么下面用图片来解释B树的插入原理,并进行一次模拟

B树的插入分析

假设此时的M = 3,也就是这是一个三叉树,那么从上面的规则来说,每个节点要存储两个数据,还有三个孩子节点,而实际上的过程中会分别多创建一个节点,也就是说会创建三个数据域和四个孩子节点,这样的好处后续在实现代码的过程中会体现出来

假设现在给定了这样的一组数据:53, 139, 75, 49, 145, 36, 101

图解如下:

数据结构:图解手撕B-树以及B树的优化和索引,C++,数据结构,知识总结,数据结构,b树

那么超过了可以容纳的数据个数,该如何处理呢?看B树的规则是如何处理的:

B树的分裂规则:

当超过了最多能容纳的数据个数后,会进行分裂:

  1. 找到节点数据域的中间位置
  2. 创建一个兄弟节点,把后一半的数据挪动到兄弟节点中
  3. 把中位数的数据移动到父节点中
  4. 对这些节点建立链接

数据结构:图解手撕B-树以及B树的优化和索引,C++,数据结构,知识总结,数据结构,b树

此时就完成了B树的一次分裂,从中就能看出B树的基本原理,既然是多叉搜索树,那么也要满足搜索树的规则,因此采取这样的分裂规则是可以满足搜索树的要求的

继续进行插入数据,按照上述的原理即可

数据结构:图解手撕B-树以及B树的优化和索引,C++,数据结构,知识总结,数据结构,b树
当继续插入的时候,就会产生新的分裂问题:

由此得出了最终的生成图

数据结构:图解手撕B-树以及B树的优化和索引,C++,数据结构,知识总结,数据结构,b树

从这个图中也能看出,确实是符合搜索树的预期的,那么下一步就是要把上面写的这一系列的过程转换成代码来进行实现

#include <iostream>
using namespace std;

// 定义B树节点的信息
template <class K, size_t M>
struct BTreeNode
{
	// 节点内部包含一个数组用来存储数据域信息,和一个指针数组用来保存孩子节点信息,以及双亲的信息
	// 还要包括节点中已经存储的数据的数量
	// 多开辟一个空间,方便于判断是否需要进行分裂
	K _keys[M];
	BTreeNode<K, M>* _subs[M + 1];
	BTreeNode<K, M>* _parent;
	size_t _n;

	BTreeNode()
		:_parent(nullptr)
		, _n(0)
	{
		for (int i = 0; i < M; i++)
		{
			_subs[i] = nullptr;
			_keys[i] = nullptr;
		}
		_subs[M] = nullptr;
	}
};

// 存储B树的信息
template <class K, size_t M>
class BTree
{
	typedef BTreeNode<K, M> Node;
public:
	// 查找函数,找某个确定的Key值,如果找到了返回它所在的节点和所处节点的位置
	pair<Node*, int> Find(const K& key)
	{
		Node* parent = nullptr;
		Node* cur = _root;
		// 开始寻找
		while (cur)
		{
			size_t i = 0;
			// 指针到每一层的节点后进行比较
			while (i < cur->_n)
			{
				if (key < cur->_keys)
				{
					// 说明此时要查找的节点信息不在这一层,一定是要到下面一层去找,因此跳出这一层的循环
					break;
				}
				else if (key > cur->_keys)
				{
					// 说明此时要查找的信息可能在当前查找的节点的后面,还要去后面找找看
					i++;
				}
				else
				{
					// 说明此时找到节点的信息了,直接把节点的信息进行返回即可
					return make_pair(cur, i);
				}
			}
			// 说明此时这一层已经找完了,现在该去下一层进行寻找了
			parent = cur;
			// 由B树的性质得出,subs[i]中存储的信息是比当前信息要小的树,因此去这里寻找目标Key值
			cur = cur->_subs[i];
		}

		// 运行到这里就是这个值在B树中不存在,返回查找最后的层数的节点和错误值即可
		return make_pair(parent, -1);
	}

	// 把元素插入到表中,本质上是一种插入排序
	void InsertKey(Node* node, const K& key, Node* child)
	{
		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;
			}
		}

		// 把值写入到节点中
		node->_keys[end + 1] = key;
		node->_subs[end + 2] = child;
		// 如果有孩子节点,那么要更新孩子节点的指向,插入元素后双亲所在的位置发生了变化
		if (child)
			child->_parent = node;
		node->_n++;
	}

	bool Insert(const K& key)
	{
		// 如果_root是一个空树,那么直接创建节点再把值放进去即可
		if (_root == nullptr)
		{
			_root = new Node;
			_root->_keys[0] = key;
			_root->_n++;
			return true;
		}

		// 运行到这里,说明这个树不是一个空树,那么首先要寻找插入的节点在现有的B树中是否存在
		pair<Node*, int> ret = Find(key);
		if (ret.second != -1)
		{
			// 键值对的第二个信息不是-1,说明在B树中找到了要插入的信息,这是不被允许的,因此返回
			return false;
		}

		// 运行到这里,说明要开始向B树中插入新节点了
		// 并且前面的ret还找到了parent,也就是实际应该是插入的位置信息
		Node* parent = ret.first;
		K newKey = key;
		// 创建孩子指针的意义是,后续可能会重复的进行分裂情况,并且插入元素的节点中可能原先有值
		// 直接插入后,会把原来孩子节点的双亲节点发生替换,因此要改变孩子节点的指向
		Node* child = nullptr;
		while (1)
		{
			// 此时就找到了要插入的元素,要插入的位置,进行插入
			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->_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;
	}
private:
	Node* _root = nullptr;
};

B+树和B*树

B+树

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

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

数据结构:图解手撕B-树以及B树的优化和索引,C++,数据结构,知识总结,数据结构,b树
B+树的特性:

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

B*树

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

数据结构:图解手撕B-树以及B树的优化和索引,C++,数据结构,知识总结,数据结构,b树

分裂原理

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

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

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

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

B树的应用

B树的最常见应用就是当做索引

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

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

数据结构:图解手撕B-树以及B树的优化和索引,C++,数据结构,知识总结,数据结构,b树文章来源地址https://www.toymoban.com/news/detail-833979.html

到了这里,关于数据结构:图解手撕B-树以及B树的优化和索引的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】16 二叉树的定义,性质,存储结构(以及先序、后序、中序遍历)

    一个二叉树是一个有穷的结点集合。 它是由根节点和称为其左子树和右子树的两个不相交的二叉树组成的。 二叉树可具有以下5种形态。 一个二叉树第i层的最大结点数为 2 i − 1 2^{i-1} 2 i − 1 , i ≥ 1 i geq 1 i ≥ 1 每层最大结点可以对应完美二叉树(满二叉树),其所有分支结

    2024年02月20日
    浏览(45)
  • 【MySQL数据库 | 第十七篇】索引以及索引结构介绍

    目录 前言: 索引简介:  索引结构:           二叉树索引结构         Tree(普通二叉树)         B-Tree(多路平衡查找树)         B+Tree          哈希索引数据结构 总结: 在实际生活中,我们对SQL语句进行优化实际上有很大一部分都是对索引进行优化,因此对索引

    2024年02月09日
    浏览(76)
  • 【MySQL索引与优化篇】InnoDB数据存储结构

    索引结构给我们提供了高效的索引方式,不过索引信息以及数据记录都是保存在文件上的,确切说是存储在页结构中。另一方面,索引是在存储引擎中实现的,MySQL服务器上的 存储引擎 负责对表中数据的读取和写入工作。不同存储引擎中 存放的格式 一般是不同的。 由于 I

    2024年02月07日
    浏览(53)
  • MySQL 底层数据结构 聚簇索引以及二级索引 Explain的使用

    我们知道MySQL的存储引擎Innodb默认底层是使用B+树的变种来存储数据的 下面我们来复习一下B树存储 + B树存储  + 哈希存储的区别 哈希存储,只能使用等值查询 B树与B+树存储 我们知道B+树实际上就是B树的变种 那么为啥使用B+树而不是使用B树呢? 我们知道效率的高低主要取决于

    2024年04月28日
    浏览(43)
  • 【数据结构之树】——什么是树,树的特点,树的相关概念和表示方法以及在实际的应用。

    树是一种非线性的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因 为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。 1.有一个特殊的结点,称为根结点,根节点没有前驱结点 2.除根节点外,其余结点被分成M(M0)个互不相交的

    2024年02月02日
    浏览(49)
  • 14-数据结构-二叉树的创建以及前中后遍历,以及结点和叶子节点的计算(C语言)

    概述:         二叉树,这里采用孩子链表存储法,即一个数据域和两个左右孩子指针域。随后递归进行遍历即可。在创建二叉树的时候,先创建各个二叉树结点(这里的结点采用动态分配,因此结点为指针变量),随后,再根据逻辑结构图,手动通过左右指针域,链接到对

    2024年02月11日
    浏览(45)
  • 【数据结构】-快速排序的四种方法实现以及优化

    作者:小树苗渴望变成参天大树 作者宣言:认真写好每一篇博客 作者gitee:gitee 如 果 你 喜 欢 作 者 的 文 章 ,就 给 作 者 点 点 关 注 吧! 今天讲一种不一样的排序,听名字就知道这个排序不拐弯抹角的,我们来看看它又多快速,并且快速排序的前三种方法都是递归思想,

    2024年02月03日
    浏览(47)
  • 数据结构与算法学习:二叉树的后序遍历的递归与非递归实现,以及非递归实现中的流程控制的说明。

    需求二叉树: 采用二叉树后序遍历非递归算法。设置一个指针p初始指向树根,p先入栈,而后使得p指向它的左孩子p-firstchild,重复操作,使得每个左孩子都依次入栈,同时初始化一个Treenode*类型的指针 pre,这个指针是后序前驱,这个后序前驱用以区分为已访问过的结点和未

    2023年04月22日
    浏览(49)
  • 【数据结构】—— 队列基础知识以及数组模拟队列的分析、演示及优化

    ❤️一名热爱Java的大一学生,希望与各位大佬共同学习进步❤️ 🧑个人主页:@周小末天天开心 各位大佬的点赞👍 收藏⭐ 关注✅,是本人学习的最大动力 感谢! 📕该篇文章收录专栏—数据结构 目录 什么是队列? 数组模拟队列 分析 存入队列的步骤 使用数组模拟队列—

    2024年01月19日
    浏览(60)
  • 【数据结构与算法】如何对快速排序进行细节优化以及实现非递归版本的快速排序?

    君兮_的个人主页 即使走的再远,也勿忘启程时的初心 C/C++ 游戏开发 Hello,米娜桑们,这里是君兮_,国庆长假结束了,无论是工作还是学习都该回到正轨上来了,从今天开始恢复正常的更新频率,今天为大家带来的内容是快速排序的两大优化和非递归实现 好了废话不多说,开

    2024年02月08日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包