B+Tree

• B+树是为磁盘或其他直接存取辅助设备设计的一种平衡查找树。在B+树中，所有记录节点都是按照键值的大小顺序存放在同一层的叶子节点上，由各叶子节点指针进行连接。
• B+树索引是B+树在数据库中的一种实现，是最常见也是数据库中使用最为频繁的一种索引。B+树中的B代表平衡（balance），而不是二叉（binary），因为B+树是从最早的平衡二叉树演化而来的。在讲B+树之前必须先了解二叉查找树、平衡二叉树（AVLTree）和平衡多路查找树（B-Tree），B+树即由这些树逐步优化而来。

为什么InnoDB存储引擎使用B+Tree？

• 减少IO读取次数
• B+Tree相对于B-Tree可以大大降低层数，也就降低了IO次数
• B+Tree每个节点可以存储很多个key（16k/key的大小，只有叶子节点才存储数据），一次io读取一页（每个节点）的所有key，在内存遍历耗时较少（相对io）
• 索引分为辅助索引与聚集索引，数据库中聚集索引只有一个，默认主键。其他用户创建的索引都是非聚集索引。而非聚集索引的叶子节点只会存储主键的键值，所以需要二次查找索引
• 辅助索引和聚集索引：

存储数据最小单元

名称	最小单元	大小
计算机磁盘存储数据	扇区	512字节
文件系统（XFS/EXT4）	块	4k
InnoDB存储引擎	页（page）	16k

image.png

B-Tree

一棵m阶的B-Tree有如下特性：

1. 每个节点最多有m个孩子。
2. 除了根节点和叶子节点外，其它每个节点至少有Ceil(m/2)个孩子。
3. 若根节点不是叶子节点，则至少有2个孩子
4. 所有叶子节点都在同一层，且不包含其它关键字信息
5. 每个非终端节点包含n个关键字信息（P0,P1,…Pn, k1,…kn）
6. 关键字的个数n满足：ceil(m/2)-1 <= n <= m-1
7. ki(i=1,…n)为关键字，且关键字升序排序。

8. Pi(i=1,…n)为指向子树根节点的指针。P(i-1)指向的子树的所有节点关键字均小于ki，但都大于k(i-1)

   
   image.png

B+Tree

• B+Tree相对于B-Tree有几点不同：

  1. 非叶子节点只存储键值信息。
  2. 所有叶子节点之间都有一个链指针。
  3. 数据记录都存放在叶子节点中。

• InnoDB存储引擎中有页（Page）的概念

  • 页是其磁盘管理的最小单位。InnoDB存储引擎中默认每个页的大小为16KB，可通过参数innodb_page_size将页的大小设置为4K、8K、16K。
  • 而系统一个磁盘块的存储空间往往没有这么大，因此InnoDB每次申请磁盘空间时都会是若干地址连续磁盘块来达到页的大小16KB。
  • InnoDB在把磁盘数据读入到磁盘时会以页为基本单位，在查询数据时如果一个页中的每条数据都能有助于定位数据记录的位置，这将会减少磁盘I/O次数，提高查询效率。
  • 对于B-Tree而言，每个节点都要存储数据的Key和Data，而每页（每个节点）的存储空间是有限的（16k），如果data较大时就会导致每页能存储的key很少，即会导致树的深度较大，增大查询的io次数。B+树的高度度一般都在 2~4层，这也就是说查找某一键值的行记录时最多只需要 2到4次IO， 因为当前一般的机械硬盘每秒至少可以做100次IO，2~4 次的IO意味查询时间只需 0.02 ~ 0.04 秒。

• 假如，使用mysql增加索引，索引列为long类型（8个字节），每个页（节点）可以存储16kb/(8B+8B)=1000个键，既为m=1000（m为1000的B+树）。以此类推，第一层存储1000，第二层存储1000x1000，第三层存储1000x1000x1000。

• b+树示例图

  
  image.png

数据库中的B+Tree索引可以分为聚集索引（clustered index）和辅助索引（secondary index）。上面的B+Tree示例图在数据库中的实现即为聚集索引，聚集索引的B+Tree中的叶子节点存放的是整张表的行记录数据。辅助索引与聚集索引的区别在于辅助索引的叶子节点并不包含行记录的全部数据，而是存储相应行数据的聚集索引键，即主键。当通过辅助索引来查询数据时，InnoDB存储引擎会遍历辅助索引找到主键，然后再通过主键在聚集索引中找到完整的行记录数据。而数据库中聚集索引只有一个，默认主键。其他用户创建的索引都是非聚集索引。

• 键值重复时，采用“溢出页”的方式处理。
  为了简化问题，B+树算法的研究一般都假设不存在键值重复的情况。现有处理重复键值的方法主要采用“溢出页”：当某个数据键值对应的记录数大于 1 时，分配一个“溢出页” 用来存放所有的重复键值及其对应记录的偏移量。

  
  image.png

使用索引

WHERE

• 以mysql来举例，完成一次检索的过程如下：

1. 检索第一层：获取到1000个键
2. 遍历（由于是有序的可以使用多分法）确定区间，或取到第二层的节点地址。
3. 检索第二层：通过获取到的节点地址获取到1000个键，重复第2、3步，直致叶子阶段。
4. 获取叶子节点的data（这里的data其实是主键）

GROUP BY （紧凑索引扫描）

1. 检索获取到第一个叶子节点
2. 通过叶子节点之间的底层指针遍历获取下一个叶子节点。
3. 遇到相同的叶子节点，归为一组

• 所以在使用GROUP BY 时，是要检索所有的叶子节点的，如果没有配合LIMIT 语句，开销是很大的。

参考链接

• Innodb的B+树如何处理重复key
• BTree和B+Tree详解
• 一文彻底搞懂MySQL基础：B树和B+树的区别