B树

常见的搜索结构

种类 数据格式 时间复杂度
顺序查找 无要求 O(N)
二分查找 有序 O(log2N)
二叉搜索树 无要求 O(N)
二叉平衡树（红黑树/AVL树） 无要求 O(log2N)
哈希 无要求 O(1)

以上结构适合用于数据量相对不是很大，能够一次性存放在内存中，进行数据查找的场景。如果数据量很大，比如有 100 G 数据，无法一次放进内存中，那就只能放在磁盘上了，如果放在磁盘上，需要搜索某些数据，应如何处理呢？我们可以考虑将存放关键字及其映射的数据的地址放到一个内存中的搜索树的节点中，访问数据时，先取这个地址去磁盘访问数据。

在这里插入图片描述

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

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

使用哈希表的缺陷：

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

如何加速对数据的访问呢？

提高IO的速度(SSD相比传统机械硬盘快了不少，但是还是没有得到本质性的提升)；降低树的高度——多叉树平衡树。

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+1 。n为结点中关键字的个数，满足ceil(m/2)-1≤n≤m-1。

与平衡搜索树相比，B树 压缩高度，二叉变多叉；一个节点里有多个关键字及映射的值。

B树的插入

插入分析

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

在这里插入图片描述

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

在这里插入图片描述

分裂节点：

  1. 节点数据域的中间位置的数据给父亲节点，如果没有父亲节点就创建。
  2. 创建兄弟节点，将数据域的另一半数据给兄弟节点。
  3. 连接好各节点。

在这里插入图片描述

每次插入需要检查节点数据是否已满，满了就要分裂。

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

总结：

  1. 如果树为空，直接插入新节点中，该节点为树的根节点。
  2. 树非空，找待插入元素在树中的插入位置（注意：找到的插入节点位置一定在叶子节点中）。
  3. 检测是否找到插入位置（假设树中的key唯一，即该元素已经存在时则不插入）。
  4. 按照插入排序的思想将该元素插入到找到的节点中。
  5. 检测该节点是否满足B树的性质：即该节点中的元素个数是否等于M，如果小于则满足。
  6. 如果插入后节点不满足B树的性质，需要对该节点进行分裂。
插入代码实现
namespace mine
{
	template<class K, size_t M>
	struct BTreeNode
	{
		K _keys[M];  //节点的关键字
		BTreeNode<K, M>* _sub[M + 1]; //指向孩子节点的指针
		BTreeNode<K, M>* _parent; //前驱指针
		size_t n;    //记录当前节点的关键字数量

		BTreeNode()
		{
			for (int i = 0;i < M;i++)
			{
				_keys[i] = K();
				_sub[i] = nullptr;
			}
			_sub[M] = nullptr;
			_parent = nullptr;
			n = 0;
		}
	};
	template<class K, size_t M>
	class BTree
	{
		typedef BTreeNode<K, M> Node;
	public:
		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[i])
						break;
					else if (key > cur->_keys[i])
						i++;
					else
						return make_pair(cur, i);//找到后返回key所在节点地址和下标
				}
				parent = cur;
				cur = cur->_sub[i];
			}
			return make_pair(parent, -1);//未找到返回叶子节点
		}

		void InsertKey(Node* node, const K& key, Node* child)//完成key插入节点
		{
			int end = node->n - 1;
			while (end >= 0)//循环后end为插入位置的前一个位置
			{
				if (key < node->_keys[end])//挪动数据
				{
					node->_keys[end + 1] = node->_keys[end];
					node->_sub[end + 2] = node->_sub[end + 1];
					end--;
				}
				else //大于
					break;
			}
			node->_keys[end + 1] = key; //插入key
			node->_sub[end + 2] = child;//node不是叶子节点，child节点不为空
			if (child)//处理child的前驱指针
			{
				child->_parent = node;
			}
			node->n++;
		}

		bool insert(const K& key)
		{
			if (_root == nullptr)//空树
			{
				_root = new Node;
				_root->_keys[0] = key;
				_root->n++;
				return true;
			}

			pair<Node*, int> ret = Find(key);//key是否已存在
			if (ret.second >= 0)//key已存在，不再插入
				return false;

			//key不存在，用ret返回的待插入的叶子节点的地址
			Node* cur = ret.first;
			Node* child = nullptr;
			K newkey = key;

			while (1)
			{
				InsertKey(cur, newkey, child);//往cur节点插入key
				if (cur->n < M)//未满
					return true;

				//满了，分裂
				int mid = M / 2;
				//[mid+1,M-1]给brother
				Node* brother = new Node;
				int j = 0;
				int i = mid + 1;
				for (;i <= M - 1;i++)
				{
					brother->_keys[j] = cur->_keys[i];
					brother->_sub[j] = cur->_sub[i];

					if (cur->_sub[i])//处理被拷贝部分的前驱指针
						cur->_sub[i]->_parent = brother;

					cur->_keys[i] = K();//已拷贝部分重置为默认值
					cur->_sub[i] = nullptr;
					j++;
				}
				brother->_sub[j] = cur->_sub[i];//i=M，处理最后一个指针
				if (cur->_sub[i])
					cur->_sub[i]->_parent = brother;
				cur->_sub[i] = nullptr;

				//在InsertKey或下方处理brother->_parent
				brother->n = j;
				cur->n -= (brother->n + 1);

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

				if (cur->_parent == nullptr)//cur为根
				{
					_root = new Node;
					_root->_keys[0] = midkey;
					_root->_sub[0] = cur;
					_root->_sub[1] = brother;
					_root->n = 1;

					brother->_parent = _root;
					cur->_parent = _root;
					break;
				}
				else//parent不是根，把midkey插入到前驱节点
				{
					newkey = midkey;
					child = brother;
					cur = cur->_parent;
				}
			}
			return true;
		}

		void InOrder()
		{
			_InOrder(_root);
		}

	private:
		Node* _root = nullptr;

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

			int i = 0;
			for (;i < cur->n;i++)
			{
				_InOrder(cur->_sub[i]);
				cout << cur->_keys[i] << " ";
			}
			_InOrder(cur->_sub[i]);//还剩最后一个孩子
		}
	};

	void TestBTree()
	{
		int arr[] = { 53, 139, 75, 49, 145, 36, 101 };
		BTree<int, 3> bt;
		for (auto e : arr)
		{
			bt.insert(e);
		}
		bt.InOrder();
	}
}

在这里插入图片描述

B树的性能

B树的插入、删除、查找的时间复杂度为O(logMN)，定位到节点后，由于数组有序，可以用二分查找在节点内快速找到数据。

B+树

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

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

在这里插入图片描述

B+树的特性：

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

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

B*树

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

在这里插入图片描述

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

B树：有序数组 + 平衡多叉树。

B+树：有序数组链表 + 平衡多叉树。

B*树：一棵更丰满的，空间利用率更高的B+树。

B树的应用

索引

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

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

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

MySQL索引简介

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

在这里插入图片描述

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

MyISAM

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

在这里插入图片描述

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

在这里插入图片描述

MyISAM中索引检索的算法为首先按照B+树搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为

地址，读取相应数据记录。MyISAM的索引方式也叫做 非聚集索引。

InnoDB

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

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

在这里插入图片描述

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

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

在这里插入图片描述

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

# c++ # b树 # 开发语言 # 数据结构 # 算法 # 学习方法
Logo
AtomGit开源社区

AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。

更多推荐

cover

【强化学习系列·第 06 篇·终篇】未来与挑战：离线 RL、多智能体、安全 RL 与 RL 的终极目标

avatar AtomGit开源社区
cover

【RAG 系列·第 01 篇】全景图：从信息检索到知识增强——RAG 的前世今生

avatar AtomGit开源社区
cover

Linux Pulseaudio深度解析之pa_stream_get_device_name调用流程与实战(二十四)

avatar AtomGit开源社区