4.B-树

一、常见的查找方式 

顺序查找 O(N)

二分查找 O(logN)（要求有序和随机访问）

二叉搜索树 O(N)

平衡二叉搜索树(AVL树和红黑树) O(logN)

哈希 O(1)
考虑效率和要求而言，正常选用 平衡二叉搜索树 和 哈希 作为查找方式。

但这两种结构适合用于数据量相对不是很大，能够一次性存放在内存中，进行数据查找的场景。如果数据量很大，比如有100G数据，无法一次放进内存中，那就只能放在磁盘上了。

如果放在磁盘上，有需要搜索某些数据，那么如果处理呢？

可以考虑将 存放关键字及其映射的数据的地址放到一个内存中的搜索树的节点 中。需要访问数据时，先取这个地址去磁盘访问数据。

分析效率的缺陷：

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

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

使用哈希表的缺陷：

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

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

1. 提高 IO 的速度 (SSD 相比传统机械硬盘快了不少，但是还是没有得到本质性的提升 )

2. 降低树的高度 --- 多叉树平衡树

二、B树概念

1970 年， R.Bayer 和 E.mccreight 提出了一种适合外查找的树，它是一种平衡的多叉树，称为 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树的插入

抽象情况分析：

1）根为空，创建新根，插入

2）根不为空，查找key，

若存在，不插入；

若不存在，插入到对应的叶子节点，若没有满，插入结束；若满了就分裂出兄弟节点，分一半key和孩子给兄弟节点，提取key中位数，转化成向父节点插入key中位数和兄弟节点，直到父节点满足条件：没有满 或者 父节点的父节点为空，产生新的根节点。

具体情况分析：

以{53,139,75,49,145,36,50,47,101}为例：

插入53,139,75：

插入49,145,36：

插入50,47,101：

实现插入时特别注意：

1）分裂出兄弟节点时，拷贝一半key和一半孩子，最后剩一个右孩子拷贝；拷贝的孩子若不为空，要链接父节点指针。

2）兄弟节点的_n和原始节点的_n都要修正

3）兄弟节点的父指针要指向cur->parent

4）若cur的父节点为空，造新根，新根左为cur，右为brother，注意链接cur和brother的父指针。

5）若cur的父节点不为空，cur迭代到cur->parent，转化成向cur->parent插入midKey和brother。

循环直到 当前节点未满 或 造出新根（4）。

insertKey细节：用index迭代从头遍历，直到找到比index大的位置，index及以后位置都往后挪动一位，同时挪动右孩子。若index一直走到尾，说明key是最大值，在尾赋值。最后统一链接右孩子，_n++。

代码实现如下：

void insertKey(Node* cur, Node* sub, const K& key)
{
	size_t index = 0;
	while (index < cur->_n)
	{
		//key大于当前位置，往后走
		if (key > cur->_keys[index])
		{
			++index;
		}
		else
		{
			//把index及以后key往后挪动一位
			//右孩子都向右挪动一位
			for (int i = cur->_n - 1; i >= (int)index; --i)
			{
				cur->_keys[i + 1] = cur->_keys[i];
				cur->_subs[i + 2] = cur->_subs[i + 1];
			}
			cur->_keys[index] = key;
			break;
		}
	}
	if (index == cur->_n)
	{
		cur->_keys[index] = key;
	}
	//链接右孩子
	cur->_subs[index + 1] = sub;
	cur->_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);
	//不允许冗余
	if (ret.second != -1)
	{
		return false;
	}
	//cur为要插入的叶子结点
	Node* cur = ret.first;
	K newkey = key;
	Node* brother = nullptr;
	while (true)
	{
		insertKey(cur, brother, newkey);
		//未满，结束
		if (cur->_n < M)
		{
			break;
		}
		//满了，分裂出兄弟节点
		brother = new Node;
		size_t mid = M / 2;
		size_t k = 0;
		//左key1 左孩子1 ... 左keyM 左孩子M 右孩子
		for (size_t i = mid + 1; i < M; ++i)
		{
			//分一半key
			brother->_keys[k] = cur->_keys[i];
			cur->_keys[i] = K();
			//分左孩子
			brother->_subs[k] = cur->_subs[i];
			//链接父指针
			if (brother->_subs[k] != nullptr)
			{
				brother->_subs[k]->_parent = brother;
			}
			cur->_subs[i] = nullptr;
			++k;
		}
		//最后一个右孩子
		brother->_subs[k] = cur->_subs[M];
		//链接父指针
		if (brother->_subs[k] != nullptr)
		{
			brother->_subs[k]->_parent = brother;
		}
		cur->_subs[M] = nullptr;

		//修正borther的_n和cur的_n（cur->_n还要提一个中位数给parent）
		brother->_n += M - mid - 1;
		cur->_n -= M - mid;
		//brother的parent指向cur->_parent
		brother->_parent = cur->_parent;

		newkey = cur->_keys[mid];
		cur->_keys[mid] = K();
		//转换成向parent插入一个midkey和brother
		if (cur->_parent == nullptr)
		{
			_root = new Node;
			_root->_keys[0] = newkey;
			_root->_subs[0] = cur;
			_root->_subs[1] = brother;

			cur->_parent = _root;
			brother->_parent = _root;
			_root->_n++;
			break;
		}
		else
		{
			cur = cur->_parent;
		}
	}
	return true;
}

 B树的查找：

分析：每个节点的key都是有序序列，且是一维数组，支持随机访问，因此选用二分查找。

问题就是如果二分查找当前序列找不到怎么办？

二分查找如果找不到，找出来的数据是可能比key大，也可能比key小的。但由于二分查找定位的特性，找出来的数据一定是keys数组中和与key最接近的二者之一，可能在key左边，也可能在右边，判断一下就行了，比key小就在key的右孩子里找，反之在key的左孩子里找。

注：由于查找在插入时也要用，要用parent记录cur的parent，以便于走到空时能记录下叶子节点的指针。

代码试下如下：

pair<Node*, int> find(const K& key)
{
	Node* cur = _root;
	Node* parent = nullptr;

	int begin, end, mid;
	while (cur)
	{
		begin = 0;
		end = cur->_n - 1;
		//二分查找key
		while (begin <= end)
		{
			mid = begin + ((end - begin) >> 1);
			// mid key
			if (cur->_keys[mid] < key)
			{
				begin = mid + 1;
			}
			//key mid
			else if (cur->_keys[mid] > key)
			{
				end = mid - 1;
			}
			else
			{
				return { cur,mid };
			}
		}
		parent = cur;
		//没有找到，mid是有效位置
		//可能大于或者小于key
		if (cur->_keys[mid] < key)
		{
			cur = cur->_subs[mid + 1];
		}
		else
		{
			cur = cur->_subs[mid];
		}
	}
	//cur走到nullptr，没找到，返回叶子节点的指针
	return { parent,-1 };
}

B树的中序遍历：

分析：采用一个左孩子，一个关键字的方式遍历，最后遍历剩余的一个右孩子。

代码如下：

void inorder()
{
	_inorder(_root);
	cout << endl;
}
void _inorder(Node* root)
{
	if (root == nullptr)
		return;
	//左1 根1 ... 左_n 根_n 右
	for (size_t i = 0; i < root->_n; ++i)
	{
		_inorder(root->_subs[i]);
		cout << root->_keys[i] << " ";
	}
	_inorder(root->_subs[root->_n]);
}

B树性能分析：

B- 树的效率是很高的，对于 N = 62*1000000000 个节点，如果度 M 为 1024，则logM/2(​N)≤4 ，即在620 亿个元素中，如果这棵树的度为 1024 ，则需要小于 4 次即可定位到该节点，然后利用 二分查找可以快速定位到该元素，大大减少了读取磁盘的次数 。

对于一颗满的B树， 查找的时间复杂度为O(logM(N))。

四、B+树和B*树

B+树：

B+ 树是 B 树的变形，是在 B 树基础上优化的多路平衡搜索树， B+ 树的规则跟 B 树基本类似，但是又

在 B 树的基础上做了以下几点改进优化：

1）分支节点的子树指针与关键字个数相同

2）分支节点的子树指针 p[i] 指向关键字值大小在 [k[i] ， k[i+1]) 区间之间

3）所有叶子节点增加一个链接指针链接在一起（核心）

4）所有关键字及其映射数据都在叶子节点出现（核心）

分析：1）和 2）优化了B树操作的便捷性，等同于删除了第一个节点的左孩子，且2）的优化存节点的最小值，进一步提高了查找的效率。

3）和 4）优化了B树的结构，将所有关键字及其映射数据都在叶子结点出现，并且叶子节点之间相连，方便遍历。

B+ 树的特性：

1. 所有关键字都出现在叶子节点的链表中，且链表中的节点都是有序的。

2. 不可能在分支节点中命中。

3. 分支节点相当于是叶子节点的索引，叶子节点才是存储数据的数据层。

B*树：

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

B* 树的分裂：

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

总结：当一个节点满时，转移到下一个兄弟，直到所有的节点都满了，分裂新的节点。

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

总结 ：

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

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

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

在内存中做内查找： 

B树系列与哈希和平衡二叉搜索树对比：

单纯论树高度，搜索效率而言，B树快。

B树系列隐形坏处：

1）空间利用率低，消耗高

2）插入删除数据时，分裂和合并节点，那么必然挪动数据

3）在内存中而言，跟哈希和平衡二叉搜索树还是一个量级。

结论：实质上B树系列在内存中体现不出优势。

五、B-树的应用

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

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

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

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

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

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

MyISAM 的索引文件仅仅保存数据记录的 地址 。 在 MyISAM 中，主索引和辅助索引（ Secondary key ）在结构上没有任何区别，只是主索 引要求 key 是唯一的，而辅助索引的 key 可以重复。

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

分支节点只存储key，比较小。

分支节点映射的磁盘块就可以尽可能加载Cache。

对于SQL分析：

update stuInfo set age = 35 where stuID = 50

update stuInfo set age = 35 where name = 'Rose'

这两句SQL语句的性能不同。

第一种，stuID为主键，主索引，结构是一颗B+树，查找效率为O(logM(N))

第二种，name不是主键，且没有索引，查找时暴力遍历，效率O(N)

若想经常用name进行查找， 给name创建普通索引，相当于使用name做key创建一颗B+树，value指向磁盘数据，这时候查找效率就高了。

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

1）B+树所有值都在叶子，遍历很方便，方便区间查找。

2）对于没有建立索引的字段，全表扫描很方便。

3）分值节点存储key，一个分支节点占用空间更少，可以尽可能加载到缓存。

B树优势：不用带叶子就能查找到值，但B+树高度不高，效率差别不大。

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

第一个区别是 InnoDB 的数据文件本身就是索引文件 。 MyISAM 索引文件和数据文件是分离的， 索引文件仅保存数据记录的地址 。

最大区别：每个叶子节点数据都是以文件形式存到磁盘上，数据和主键索引放在一起。 叶节点包含了完整的数据记录， 这种索引叫做聚集索引 。

所以 InnoDB 要求表必须有主键（ MyISAM 可以没有）， 如果没有显式指定，则 MySQL 系统会自动选择一个可以唯一标识数据记录的列作为主键， 如果不存在这种列，则 MySQL 自动为 InnoDB 表生成一个隐含字段作为主键，这个字段长度为6 个字节，类型为长整型。

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

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