高阶数据结构——B树_b树索引构建

1. 常见的搜索结构

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

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

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

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

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

2. B树概念

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，如下图所示。

二叉树的示例图：

3. B-树的插入分析

为了简单起见，假设M = 3. 即三叉树，所以每个结点应该包含两个关键字和三个孩子指针。但是为了方便写代码，我们增加一个关键字和孩子指针。

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

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

前两个直接插入即可。

插入第三个时，则不满足我们的条件，每个结点最多只能有k - 1个关键字，所以这里要进行分裂。

分裂步骤：

• 分裂出一个兄弟结点，并拷贝一半的关键字和孩子指针给兄弟结点。
• 提取中位数给父亲，没有父亲则创建。
• 将根结点，兄弟结点和当前结点进行连接。

中位数是75，所以将75后边的所有值拷贝给兄弟，而当前结点没有父亲结点，所以还要创建一个父亲结点，并将75拷给父亲。

注意，B是是一颗平衡搜索树，所以插入时要注意插入位置，保持有序。

插入36时，我们会发现，左下角的那个结点满了，此时又需要分裂，将中位数49给他的父亲，49后面的数给他的兄弟结点。

右下角的结点又不满足B树的条件了，开始分裂，和前面一样，将139交给父亲，145给兄弟结点。

此时，我们发现，根节点又不满足B树性质了，我们要对根节点进行分裂，如下图所示。

4. B树的插入实现

4.1 插入key的过程

我们可以将插入的过程分为这几步。

• 1. 判断树是否为空，为空则需要创建根结点。
• 2. 找到要插入的结点（一定为叶子结点）。
• 3. 将key插入到结点中。
• 4. 判断当前结点是否满了，如果满了，则需要开始分裂，没满则结束。
• 5. 如果当前结点是根节点（没有父亲），则重新创建一个结点当根，并连接好相应关系，如果不是根节点，则将当前结点的中位数当作key，要插入的结点变成了当前结点的父亲，回到第三步。

1 - 4步很好理解，可以对照前面的图来分析，第5步不好理解，我们举两个例子来看。

1. 当前结点是根节点

例如这里，我们插入75，已经完成了第三步了，第四步是分裂，将一半的值拷贝给他的兄弟。

还有最后的一步，我们就可以完成这个插入过程了，即将75给当前结点的父结点。但是当前结点没有父结点，所以我们直接创建一个新结点当作根结点即可。

当前结点不是根节点

如果插入的是36，还是一样要分裂一半给他兄弟。

现在我们需要将75插入父亲结点，我们会发现插入父结点和插入当前结点的逻辑其实都是一样的，所以我们，在分裂完之后，要将75当成新的key插入到父亲结点当中（一个很重要的逻辑）。所以我们现在又要到第三步去将75插入父亲结点。

第三步执行完，到第四步，发现父亲结点还没有满，插入过程结束。

4.2 B树结点的设计

//K是数据类型，M是树的路数，将来就是M叉树
template<class K, size_t M>
struct BTreeNode
{
	BTreeNode()
	{
		for (size_t i = 0; i < M; i++)
		{
			_keys[i] = K();
			_chlids[i] = nullptr;
		}
		_childs[M] = nullptr;
		_parent = nullptr;
		_size = 0;
	}
 
	//为了方便写代码，所以关键字和孩子指针我们都多开了一个空间。
	K _keys[M];  //关键字
	BTreeNode<K, M>* _childs[M + 1]; //孩子指针
	BTreeNode<K, M>* _parent;        //父亲指针
	size_t _size; //实际存储的个数
};

我们使用一个类模板来适配各种类型，M表示树的路树，一个B树的结点中包含以下几个内容：

• 1. _keys用来保存关键字的数组。
• 2. _childs是孩子的指针，指向他的孩子结点。
• 3. _parent是父亲指针，将来可以很容易找到当前结点的父亲。
• 4. _size是保存的关键字个数，也可以得到孩子的个数（B树结点中，孩子的数量永远比关键字多一个）。

4.3 B树的插入实现

B树的插入过程：

• 1. 判断树是否为空，为空则需要创建根结点。
• 2. 找到要插入的结点（一定为叶子结点）。
• 3. 将key插入到结点中。
• 4. 判断当前结点是否满了，如果满了，则需要开始分裂，没满则结束。
• 5. 如果当前结点是根节点（没有父亲），则重新创建一个结点当根，并连接好相应关系，如果不是根节点，则将当前结点的中位数当作key，要插入的结点变成了当前结点的父亲，回到第三步。

bool Insert(const K& key)
{
	//1.如果是一颗空树，创建一个新结点即可。
	if (_root == nullptr)
	{
		_root = new Node();
		_root->_keys[0] = key;
		_root->_size++;
 
		return true;
	}
 
	//2.每次插入都是往叶子结点插入，所以先找到要插入的叶子结点。
	pair<Node*, int> ret = Find(key);
	if (ret.second >= 0)
	{
		//找到了一个值为key的结点，不需要再插入了（当前B树不支持插入重复值）
		return false;
	}
 
	//3.将key插入结点中
	//ret顺便将key应该插入的结点带回来了，我们直接将key插入该结点即可
	Node* cur = ret.first;
	K insertKey = key;
	Node* insertChild = nullptr;
	InsertKey(cur, insertKey, insertChild);
 
	return true;
}

上面的代码已经完成了前三步的动作了，而第二步和第三步中的Find和InsertKey的函数我们还需要手动实现一下。

//返回一个pair，第一个参数是要查找的那个结点，第二个参数是要查找的位置下标，为-1表示查找失败。
pair<Node*, int> Find(const K& key)
{
	Node* cur = _root;
	Node* parent = nullptr;
	while (cur != nullptr)
	{
		size_t i = 0;
		parent = cur;
		while (i < cur->_size)
		{
			if (cur->_keys[i] > key)       //向当前结点的孩子去查找
			{
				break;
			}
			else if (cur->_keys[i] < key)  //比当前值大，继续向后查找
			{
				i++;
			}
			else
			{
				return make_pair(cur, i);  //查找成功，返回结果
			}
		}
		cur = cur->_childs[i]; //向当前结点的孩子去查找。
	}
 
	//查找失败，不存在值为key的结点，我们将parent返回，为了方便以后将key插入parent
	return make_pair(parent, -1);
}

首先是Find函数，以下图为例：

现在我们需要找到36要插入的结点，cur指向的就是最上面那个结点，从左向右判断，发现36比75小，那么就进入75对应下标的childs，也就是childs[0]，cur指向了右下角那个结点，再次从左往右判断，发现比49小，于是进入49对应下标的childs，也就是childs[0]，此时cur是nullptr，循环结束，我们此时需要返回cur的parent，也就是左下角的结点，这个结点也就是将来36要插入的结点。

void InsertKey(Node* cur, const K& key, Node* child)
{
	auto& childs  = cur->_childs;
	auto& keys = cur->_keys;
	size_t size = cur->_size - 1;
 
	while (size >= 0)
	{
		if (keys[size] > key)
		{
			//将keys[size+1]和childs[size+2]向后移动，为了给key和child提供位置。
			keys[size + 1] = keys[size];
			childs[size + 2] = childs[size + 1];
		}
		else
		{
			break;
		}
 
		size--;
 
	}
 
	//将key和child插入进cur->_keys和cur->_childs中去。
	keys[size + 1] = key;
	childs[size + 2] = child;
 
	//不要忘记修改孩子的父亲
	if (child)
		child->_parent = cur;
 
	//新插入了一个key，所以size要加1
	cur->_size++;
}

将一个值和孩子插入一个结点，我们使用的是直接插入排序，如下图所示。

需要注意的是，不仅仅需要插入key，而且还需要插入child，因为B树的性质就是key永远比child少一个，也不要忘记插入结点的父亲指针需要改变。

现在我们可以开始实现第4和第5步了：

• 4. 判断当前结点是否满了，如果满了，则需要开始分裂，没满则结束。
• 5. 如果当前结点是根节点（没有父亲），则重新创建一个结点当根，并连接好相应关系，如果不是根节点，则将当前结点的中位数当作key，要插入的结点变成了当前结点的父亲，回到第三步。

bool Insert(const K& key)
{
	//1.如果是一颗空树，创建一个新结点即可。
	if (_root == nullptr)
	{
		_root = new Node();
		_root->_keys[0] = key;
		_root->_size++;
 
		return true;
	}
 
	//2.每次插入都是往叶子结点插入，所以先找到要插入的叶子结点。
	pair<Node*, int> ret = Find(key);
	if (ret.second >= 0)
	{
		//找到了一个值为key的结点，不需要再插入了（当前B树不支持插入重复值）
		return false;
	}
 
	//3.将key插入结点中
	//ret顺便将key应该插入的结点带回来了，我们直接将key插入该结点即可
	Node* cur = ret.first;
	K insertKey = key;
	Node* insertChild = nullptr;
 
	InsertKey(cur, insertKey, insertChild);
 
	4.如果没满就退出，满了就需要分裂
	if (cur->_size < M)
	{
		break;
	}
	else 
	{
		//创建兄弟结点，拷贝一半的值给兄弟。
		Node* brother = new Node;
		size_t mid = cur->_size / 2;
		size_t k = 0;
		for (size_t i = mid + 1; i < cur->_size; i++)
		{
			brother->_keys[k] = cur->_keys[i];       //将关键字拷贝给兄弟
			brother->_childs[k] = cur->_childs[i];   //将孩子拷给兄弟
			if (cur->_childs[i])
				cur->_childs[i]->_parent = brother;  //将孩子的父亲改成兄弟
			k++;
 
			cur->_keys[i] = K();       //设置为默认值，方便观察
			cur->_childs[i] = nullptr;
		}
		brother->_childs[k] = cur->_childs[cur->_size];  //将最后一个孩子拷给兄弟
		if (cur->_childs[cur->_size]) 
			cur->_childs[cur->_size]->_parent = brother; //将孩子的父亲改成兄弟。
		cur->_childs[cur->_size] = nullptr;
		brother->_size += k;  //更改兄弟结点的关键字个数
		cur->_size -= k;   //当前结点的关键字数要减去拷贝给兄弟的。
 
		size_t midKey = cur->_keys[mid];  //将中位数保存起来
		cur->_keys[mid] = K();
		cur->_size--;      //当前结点的关键字数还要减去拷贝给父亲的。
	}
 
	return true;
}

先来看第四步，第四步是要将一半的结点拷贝给兄弟，代码如上图所示，为了方便观察，我们将拷贝过的值设置为默认值。注意的是，B树的指针错综复杂，需要非常小心，不然很容易出错。

如何实现第五步，第五步的思想是将父结点当作一个新节点，也就是有了循环的思想，所以我们可以将3-5步放到一个循环中去。

bool Insert(const K& key)
{
	//1.如果是一颗空树，创建一个新结点即可。
	if (_root == nullptr)
	{
		_root = new Node();
		_root->_keys[0] = key;
		_root->_size++;
 
		return true;
	}
 
	//2.每次插入都是往叶子结点插入，所以先找到要插入的叶子结点。
	pair<Node*, int> ret = Find(key);
	if (ret.second >= 0)
	{
		//找到了一个值为key的结点，不需要再插入了（当前B树不支持插入重复值）
		return false;
	}
 
	//3.将key插入结点中
	//ret顺便将key应该插入的结点带回来了，我们直接将key插入该结点即可
	Node* cur = ret.first;
	K insertKey = key;
	Node* insertChild = nullptr;
 
	while (1)
	{
		InsertKey(cur, insertKey, insertChild);
 
		4.如果没满就退出，满了就需要分裂
		if (cur->_size < M)
		{
			break;
		}
		else 
		{
			//创建兄弟结点，拷贝一半的值给兄弟。
			Node* brother = new Node;
			size_t mid = cur->_size / 2;
			size_t k = 0;
			for (size_t i = mid + 1; i < cur->_size; i++)
			{
				brother->_keys[k] = cur->_keys[i];       //将关键字拷贝给兄弟
				brother->_childs[k] = cur->_childs[i];   //将孩子拷给兄弟
				if (cur->_childs[i])
					cur->_childs[i]->_parent = brother;  //将孩子的父亲改成兄弟
				k++;
 
				cur->_keys[i] = K();       //设置为默认值，方便观察
				cur->_childs[i] = nullptr;
			}
			brother->_childs[k] = cur->_childs[cur->_size];  //将最后一个孩子拷给兄弟
			if (cur->_childs[cur->_size]) 
				cur->_childs[cur->_size]->_parent = brother; //将孩子的父亲改成兄弟。
			cur->_childs[cur->_size] = nullptr;
			brother->_size += k;  //更改兄弟结点的关键字个数
			cur->_size -= k;   //当前结点的关键字数要减去拷贝给兄弟的。
 
			size_t midKey = cur->_keys[mid];  //将中位数保存起来
			cur->_keys[mid] = K();
			cur->_size--;      //当前结点的关键字数还要减去拷贝给父亲的。
 
 
			//5.如果当前结点是根节点，则需要重新创建一个根。
			//  如果当前结点不是根结点，则直接将当前结点当作新结点即可。
			if (cur->_parent == nullptr)
			{
				_root = new Node;
				_root->_keys[0] = midKey;
				_root->_childs[0] = cur;
				_root->_childs[1] = brother;
				cur->_parent = _root;
				brother->_parent = _root;
				_root->_size = 1;
 
				break;
			}
			else
			{
				insertKey = midKey;
				insertChild = brother;
				cur = cur->_parent;
			}
		}
	}
 
	return true;
}

4.4 B树的简单验证

到这里B树的插入过程的代码就写完了，我们可以做一个简单的验证，和前面的例子一样{ 53, 139, 75, 49, 145, 36, 101 }，将这组数插入到树中去，最终判断结果是否和我们分析的一样。

经过调试，可以看到结果是正确的：

这样可能不太方便观察，我在这里转换。

可以看到最终的结果是正确的，我们也可以使用前序遍历，如果结果是有序的说明应该没什么大问题。

void InOrder()
{
	_InOrder(_root);
}
 
void _InOrder(Node* root)
{
	if (root == nullptr)
		return;
 
	size_t i = 0;
	for (i = 0; i < root->_size; i++)
	{
		_InOrder(root->_childs[i]);
		cout << root->_keys[i] << " ";
	}
	_InOrder(root->_childs[i]);
}

遍历结果：

4.5 B树的性能分析

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$之间，在定位到该节点后，再采用二分查找的方式可以很快的定位到该元素。

对于N = 62*1000000000个节点，如果度M为1024，则log{M/2}N <= 4，即在620亿个元素中，如果这棵树的度为1024，则需要小于4次即可定位到该节点，然后利用二分查找可以快速定位到该元素，大大减少了读取磁盘的次数

4.6 整体代码

#pragma once
 
#include <iostream>
#include <vector>
 
using namespace std;
 
//K是数据类型，M是树的路数，将来就是M叉树
template<class K, size_t M>
struct BTreeNode
{
	BTreeNode()
	{
		for (size_t i = 0; i < M; i++)
		{
			_keys[i] = K();
			_childs[i] = nullptr;
		}
		_childs[M] = nullptr;
		_parent = nullptr;
		_size = 0;
	}
 
	//为了方便写代码，所以关键字和孩子指针我们都多开了一个空间。
	K _keys[M];  //关键字
	BTreeNode<K, M>* _childs[M + 1]; //孩子指针
	BTreeNode<K, M>* _parent;        //父亲指针
	size_t _size; //实际存储的个数
};
 
//K是数据类型，M是树的路数，将来就是M叉树
template<class K, size_t M>
class BTree
{
	typedef BTreeNode<K, M> Node;
public:
	BTree()
		: _root(nullptr)
	{}
 
	//返回一个pair，第一个参数是要查找的那个结点，第二个参数是要查找的位置下标，为-1表示查找失败。
	pair<Node*, int> Find(const K& key)
	{
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur != nullptr)
		{
			size_t i = 0;
			parent = cur;
			while (i < cur->_size)
			{
				if (cur->_keys[i] > key)       //向当前结点的孩子去查找
				{
					break;
				}
				else if (cur->_keys[i] < key)  //比当前值大，继续向后查找
				{
					i++;
				}
				else
				{
					return make_pair(cur, i);  //查找成功，返回结果
				}
			}
			cur = cur->_childs[i]; //向当前结点的孩子去查找。
		}
 
		//查找失败，不存在值为key的结点，我们将parent返回，为了方便以后将key插入parent
		return make_pair(parent, -1);
	}
 
	void InsertKey(Node* cur, const K& key, Node* child)
	{
		auto& childs  = cur->_childs;
		auto& keys = cur->_keys;
		size_t size = cur->_size - 1;
 
		while (size >= 0)
		{
			if (keys[size] > key)
			{
				//将keys[size+1]和childs[size+2]向后移动，为了给key和child提供位置。
				keys[size + 1] = keys[size];
				childs[size + 2] = childs[size + 1];
			}
			else
			{
				break;
			}
 
			size--;
 
		}
 
		//将key和child插入进cur->_keys和cur->_childs中去。
		keys[size + 1] = key;
		childs[size + 2] = child;
 
		//不要忘记修改孩子的父亲
		if (child)
			child->_parent = cur;
 
		//新插入了一个key，所以size要加1
		cur->_size++;
	}
 
	bool Insert(const K& key)
	{
		//1.如果是一颗空树，创建一个新结点即可。
		if (_root == nullptr)
		{
			_root = new Node();
			_root->_keys[0] = key;
			_root->_size++;
 
			return true;
		}
 
		//2.每次插入都是往叶子结点插入，所以先找到要插入的叶子结点。
		pair<Node*, int> ret = Find(key);
		if (ret.second >= 0)
		{
			//找到了一个值为key的结点，不需要再插入了（当前B树不支持插入重复值）
			return false;
		}
 
		//3.将key插入结点中
		//ret顺便将key应该插入的结点带回来了，我们直接将key插入该结点即可
		Node* cur = ret.first;
		K insertKey = key;
		Node* insertChild = nullptr;
 
		while (1)
		{
			InsertKey(cur, insertKey, insertChild);
 
			4.如果没满就退出，满了就需要分裂
			if (cur->_size < M)
			{
				break;
			}
			else 
			{
				//创建兄弟结点，拷贝一半的值给兄弟。
				Node* brother = new Node;
				size_t mid = cur->_size / 2;
				size_t k = 0;
				for (size_t i = mid + 1; i < cur->_size; i++)
				{
					brother->_keys[k] = cur->_keys[i];       //将关键字拷贝给兄弟
					brother->_childs[k] = cur->_childs[i];   //将孩子拷给兄弟
					if (cur->_childs[i])
						cur->_childs[i]->_parent = brother;  //将孩子的父亲改成兄弟
					k++;
 
					cur->_keys[i] = K();       //设置为默认值，方便观察
					cur->_childs[i] = nullptr;
				}
				brother->_childs[k] = cur->_childs[cur->_size];  //将最后一个孩子拷给兄弟
				if (cur->_childs[cur->_size]) 
					cur->_childs[cur->_size]->_parent = brother; //将孩子的父亲改成兄弟。
				cur->_childs[cur->_size] = nullptr;
				brother->_size += k;  //更改兄弟结点的关键字个数
				cur->_size -= k;   //当前结点的关键字数要减去拷贝给兄弟的。
 
				size_t midKey = cur->_keys[mid];  //将中位数保存起来
				cur->_keys[mid] = K();
				cur->_size--;      //当前结点的关键字数还要减去拷贝给父亲的。
 
 
				//5.如果当前结点是根节点，则需要重新创建一个根。
				//  如果当前结点不是根结点，则直接将当前结点当作新结点即可。
				if (cur->_parent == nullptr)
				{
					_root = new Node;
					_root->_keys[0] = midKey;
					_root->_childs[0] = cur;
					_root->_childs[1] = brother;
					cur->_parent = _root;
					brother->_parent = _root;
					_root->_size = 1;
 
					break;
				}
				else
				{
					insertKey = midKey;
					insertChild = brother;
					cur = cur->_parent;
				}
			}
		}
 
		return true;
	}
 
	void InOrder()
	{
		_InOrder(_root);
	}
 
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
 
		size_t i = 0;
		for (i = 0; i < root->_size; i++)
		{
			_InOrder(root->_childs[i]);
			cout << root->_keys[i] << " ";
		}
		_InOrder(root->_childs[i]);
	}
 
private:
	Node* _root;
};

5. B+树和B*树

5.1 B+树

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

• 1. 分支节点的子树指针与关键字个数相同
• 2. 分支节点的子树指针p[i]指向关键字值大小在[k[i]，k[i+1])区间之间
• 3. 所有叶子节点增加一个链接指针链接在一起
• 4. 所有关键字及其映射数据都在叶子节点出现
• 5.分支结点存放的是叶子结点的索引
• 6.父亲用孩子的最小关键字来做索引的

B+树的特性：

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

B+树的分裂：

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

5.2 B*树

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

B*树的分裂：

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

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

5.3 总结

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

单论树的高度，查找效率来看B树系列确实不错，但是也存在一些缺点。

• 1.空间利用率低，占用的空间大。
• 2.插入和删除数据时，需要进行分裂，涉及到数据的挪动，效率低。
• 3.虽然比起红黑树等，高度更低，但是在内存中都是一个量级的，搜索效率并不比红黑树快多少（在内存中没什么优势）

6. B树的应用

6.1 索引

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

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

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

6.2 MySQL索引

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

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

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

6.2.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域。

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