本文主要是写一些数据库储存相关数据结构的相关东西，主要从以下几个方面进行介绍：

• B 树和 B+ 树的结构是怎样的?为什么我们常用 B+ 树作为索引的数据结构?

• 从数据页的角度来看,B+ 树是如何进行查询的？

• B+树如何进行记录检索？

• 普通索引和唯一索引在查询效率?

B/B+树

数据库有内存和磁盘两种存储介质，内存属于临时存储，读写速度快，但有限，而且如果断电或者程序故障奔溃会导致数据的丢失，而磁盘属于永久性存储介质，断电后数据也不会丢失，所以很多数据还是需要存储在磁盘上，但是磁盘数据的读写需要硬盘的 I/O 操作，很耗费时间，而且数据读取的最小单位是页，为了尽量减少硬盘的 I/O 会尽量将随机读写转化为顺序读写，由此产生了很多的优化和实现。

基于此，我们来了解以下 B/B+树的产生背景。二分查找是很高效的查找算法，可以达到O(log2N)的时间复杂度。假设采用二叉树作为存储索引的数据结构，如果采用二叉搜索树(Binary Search Tree)，假设搜索插入的数值为 key:

1. 如果 key 大于根节点,则在右子树中进行查找;

2. 如果 key 小于根节点,则在左子树中进行查找;

3. 如果 key 等于根节点,也就是找到了这个节点,返回根节点即可。

那么，假设对 34,22,89,5,23,77,91 创建二叉搜索树，可能会呈现：

	 				34   22						895			23		77			91

但也可能会出现下面的特殊情况

5		22    		23        		34            		77                		89                    		91

此时该二分查找规划成一个链条，查找的时间复杂度也进化为O(N)，为此人们提出了平衡二叉搜索树(AVL 树)，在二分搜索树增加了约束，每个节点的左子树和右子树的高度差不能超过 1，也就是说节点的左子树和右子树仍然为平衡二叉树。常见平衡二叉树有平衡二叉搜索树、红黑树、数堆、伸展树。

数据查询的时间主要依赖于磁盘 I/O 的次数，如果采用二叉树，即使通过平衡二叉搜索树进行了改进,树的深度也是 O(log2N)，当 n 比较大时度，深度也很高，也就意味这 I/O 操作次数多，同样会影响整体的数据查询性能。

如果将二叉树改成 M 叉树(M>2)，树的高度便可以降低。

B 树数据结构

如果用二叉树作为索引的实现结构，会让树变得很高，增加硬盘的 I/O 次数，影响数据查询的时间。因此一个节点就不能只有 2 个子节点，而应该允许有 M 个子节点 (M>2)。

B 树(Balance Tree)的出现就是为了解决这个问题，也就是平衡的多路搜索树，它的高度远小于平衡二叉树的高度。在文件系统和数据库系统中的索引结构经常采用 B 树来实现。

B 树每一个节点最多可以包括 M 个子节点，M 称为 B 树的阶。每个磁盘块中包括了关键字和子节点的指针。如果一个磁盘块中包括了 x 个关键字，那么指针数就是 x+1。对于一个 100 阶的 B 树来说,如果有 3 层的话最多可以存储约 100 万的索引数据。对于大量的索引数据来说，采用 B 树的结构是很适合。

一个 M 阶的 B 树(M>2)有以下的特性:

1. 根节点的儿子数的范围是[2,M]。

2. 每个中间节点包含 k-1 个关键字和 k 个孩子,孩子数量=关键字数量+1，k 取值范围为 [ceil(M/2), M]
   

3. 叶子节点包括 k-1 个关键字(叶子节点没有孩子)，k 的取值范围为 [ceil(M/2),M]。

4. 假设中间节点节点的关键字为:Key[1], Key[2], ..., Key[k-1]，且关键字按照升序排序,即 Key[i]<Key[i+1]。此时k-1个关键字相当于划分了k个范围,也就是对应着k个指针,即为:P[1], P[2], ..., P[k]，其中 P[1] 指向关键字小于Key[1]的子树，P[i]指向关键字属于(Key[i-1], Key[i])的子树,P[k]指向关键字大于 Key[k-1]的子树。

5. 所有叶子节点位于同一层。

假设对上图中查找关键字为 9 的数据，那么会执行下面的操作：

1. 我们与根节点的关键字 (17,35)进行比较,9 小于 17 那么得到指针 P1;

2. 按照指针 P1 找到磁盘块 2,关键字为(8,12),因为 9 在 8 和 12 之间,所以我们得到指针 P2;

3. 按照指针 P2 找到磁盘块 6,关键字为(9,10),然后我们找到了关键字 9。

B+树数据结构

B+ 树基于 B 树做出了改进，主流的 DBMS 都支持 B+ 树的索引方式，比如 MySQL。B+树和 B 树的差异在于以下几点:

1. 有 k 个孩子的节点就有 k 个关键字。也就是孩子数量 = 关键字数,而 B 树中,孩子数量 = 关键字数 +1。

2. 非叶子节点的关键字也会同时存在在子节点中，并且是在子节点中所有关键字的最大(或最小)。

3. 非叶子节点仅用于索引，不保存数据记录，跟记录有关的信息都放在叶子节点中。而 B 树中,非叶子节点既保存索引，也保存数据记录。

4. 所有关键字都在叶子节点出现，叶子节点构成一个有序链表，而且叶子节点本身按照关键字的大小从小到大顺序链接。

查找 16 关键字，自顶向下会进行下面的操作：

1. 与根节点的关键字 (1,18,35) 进行比较，16 在 1 和 18 之间，得到指针 P1(指向磁盘块 2)

2. 找到磁盘块 2，关键字为(1,8,14)，因为 16 大于 14,所以得到指针 P3(指向磁盘块 7)

3. 找到磁盘块 7,关键字为(14,16,17)，然后我们找到了关键字 16，所以可以找到关键字 16 对应的数据。

B+ 树的中间节点并不直接存储数据。可以带来下面的好处：

1. B+ 树查询效率更稳定。因为 B+ 树每次只有访问到叶子节点才能找到对应的数据，而在 B 树中,非叶子节点也会存储数据,这样就会造成查询效率不稳定的情况,有时候访问到了非叶子节点就可以找到关键字,而有时需要访问到叶子节点才能找到关键字。

2. B+ 树的查询效率更高。这是因为通常 B+ 树比 B 树更矮胖(阶数更大，深度更低),查询所需要的磁盘 I/O 也会更少。同样的磁盘页大小，B+ 树可以存储更多的节点关键字。

3. 在查询范围上,B+ 树的效率也比 B 树高。这是因为所有关键字都出现在 B+ 树的叶子节点中，并通过有序链表进行了链接。而在 B 树中则需要通过中序遍历才能完成查询范围的查找,效率要低很多。

从数据页角度理解 B+树查询

MySQL 的 InnoDB 存储引擎采用 B+ 树作为索引,而索引又可以分成聚集索引和非聚集索引(二级索引)，一棵 B+ 树按照节点类型可以分成两部分:

1. 叶子节点，B+ 树最底层的节点，节点的高度为 0，存储关键字和行记录。在节点内部(也就是页结构的内部)记录之间是一个单向的链表，但是对记录进行查找，可以通过页目录采用二分查找的方式来进行。

2. 非叶子节点，节点的高度大于 0，包括了多个索引行，索引行里存储索引键和指向下一层页面的页面指针，并不存储行记录本身。每个索引行里存储索引键和页面指针

B+ 树如何进行记录检索

如果通过 B+ 树的索引查询行记录，首先是从 B+ 树的根开始，逐层检索，直到找到叶子节点，也就是对应的数据页为止。将数据页加载到内存中，页目录中的槽(Slot)采用二分查找的方式先找到一个粗略的记录分组，然后再在分组中通过链表遍历的方式查找记录。

普通索引和唯一索引查询效率

唯一索引就是在普通索引上增加了约束性，也就是关键字唯一，找到了关键字就停止检索。而普通索引，可能会存在用户记录中的关键字相同的情况。

当我们读取一条记录的时候，需要将这个记录所在的页加载到内存中进行读取。InnoDB 存储引擎的页大小为 16KB，在一个页中可能存储着上千个记录，因此在普通索引的字段上进行查找也就是在内存中多次“判断下一条记录”的操作，对于 CPU 来说这些操作所消耗的时间是可以忽略不计的。所以对一个索引字段进行检索，采用普通索引还是唯一索引在检索效率上基本上没有差别。

参考资料

1. 极客时间专栏：陈旸《SQL 必知必会》