MySQL中的B+树索引结构

电玩女神 2022-08-29 00:26 122阅读 0赞

# B树 #

B树（B-tree、B-树）：是一种平衡的多路搜索树，多用于文件系统、数据库的实现。

## B树的特点： ##

*  1个节点可以存储超过2个元素、可以拥有超过2个子节点；
 *  拥有二叉搜索树的一些性质（有序性）；
 *  平衡，每个节点的所有子树高度一致；
 *  树的整体高度较低。

## m阶B树的性质（m≥2） ##

m阶表示节点允许有m个子节点，节点元素的个数可以有m-1个。

3阶B树：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70]

4阶B树：

![在这里插入图片描述][662676eb5c4d4470a7547d781a09de9f.png]

# B+树 #

B+树是B树的一种变形形式，B+树上的叶子结点存储关键字以及相应记录  
的地址，叶子结点以上各层作为索引使用。

![在这里插入图片描述][a98cfa326e19494aa1be84f3afe060ca.png]

从上图我们可以归纳出B+树的几个特征：

*  所有记录节点都是按键值的大小顺序存放在同一层的叶子节点上，由各叶子节点  
    指针进行连接；
 *  相同节点数量的情况下，B+树高度远低于平衡二叉树；
 *  非叶子节点只保存索引信息和下一层节点的指针信息，不保存实际数据  
    记录；
 *  只有叶子节点存储实际的数据。

B+树的变体为B*树，在B+树的非根和非叶子结点再增加指向兄弟的指针；  
B*树定义了非叶子结点关键字个数至少为(2/3)\*M，即块的最低使用率为2/3（代  
替 B+树的1/2）。

# MySQL中的B+树索引结构 #

B+树索引是数据库系统中最为常见的一种索引数据结构，几乎所有的关系型数据库都支持它。

那为什么关系型数据库都热衷支持B+树索引呢？因为它是目前为止排序最有效率的数据结构。像二叉树，哈希索引、红黑树、SkipList，在海量数据基于磁盘存储效率方面远不如B+树索引高效。

所以，上述的数据结构一般仅用于内存对象，基于磁盘的数据排序与存储，最有效的依然是B+树索引。

B+树索引的特点是： 基于磁盘的平衡树，但树非常矮，通常为3~4层，能存放千万到上亿的排序数据。树矮意味着访问效率高，从千万或上亿数据里查询一条数据，只用 3、4 次I/O。

又因为现在的固态硬盘每秒能执行至少10000次I/O，所以查询一条数据，哪怕全部在磁盘上，也只需要0.0030.004秒。另外，因为B+树矮，在做排序时，也只需要比较34次就能定位数据需要插入的位置，排序效率非常不错。

B+树索引由根节点（root node）、中间节点（non leaf node）、叶子节点（leaf node）组成，其中叶子节点存放所有排序后的数据。当然也存在一种比较特殊的情况，比如高度为1的B+树索引：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 1]

上图中，第一个列就是B+树索引排序的列，你可以理解它是表User中的列id，类型为8字节的BIGINT，所以列userId就是索引键（key），类似下表：

CREATE TABLE User (
      id BIGINT AUTO_INCREMENT PRIMARY KEY,
      name VARCHAR(128) NOT NULL,
      sex CHAR(6) NOT NULL,
      registerDate DATETIME NOT NULL,
      ...
    )

所有B+树都是从高度为1的树开始，然后根据数据的插入，慢慢增加树的高度。你要牢记：索引是对记录进行排序， 高度为1的B+树索引中，存放的记录都已经排序好了，若要在一个叶子节点内再进行查询，只进行二分查找，就能快速定位数据。

可随着插入B+树索引的记录变多，1个页（16K）无法存放这么多数据，所以会发生B+树的分裂，B+树的高度变为 2，当B+树的高度大于等于2时，根节点和中间节点存放的是索引键对，由（索引键、指针）组成。

索引键就是排序的列，而指针是指向下一层的地址，在MySQ 的InnoDB存储引擎中占用6个字节。下图显示了B+树高度为2时，B+树索引的样子：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 2]

可以看到，在上面的B+树索引中，若要查询索引键值为5的记录，则首先查找根节点，查到键值对（20，地址），这表示小于20的记录在地址指向的下一层叶子节点中。接着根据下一层地址就可以找到最左边的叶子节点，在叶子节点中根据二分查找就能找到索引键值为5的记录。

那一个高度为2的B+树索引，理论上最多能存放多少行记录呢?

在 MySQL InnoDB存储引擎中，一个页的大小为16K，在上面的表User中，键值userId是BIGINT类型，则：

根节点能最多存放以下多个键值对 = 16K / 键值对大小(8+6) ≈ 1100

再假设表User中，每条记录的大小为500字节，则：

叶子节点能存放的最多记录为 = 16K / 每条记录大小 ≈ 32

综上所述，树高度为 2 的 B+ 树索引，最多能存放的记录数为：

总记录数 = 1100 * 32 =  35,200

也就是说，35200条记录排序后，生成的B+树索引高度为2。在35200条记录中根据索引键查询一条记录只需要查询2个页，一个根叶，一个叶子节点，就能定位到记录所在的页。

高度为3的B+树索引本质上与高度2的索引一致，如下图所示，不再赘述：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 3]

同理，树高度为3的 B+ 树索引，最多能存放的记录数为：

总记录数 = 1100（根节点） * 1100（中间节点） * 32 =  38,720,000

讲到这儿，你会发现，高度为3的B+树索引竟然能存放3800W条记录。高度为4的B+树索引就能存放上百亿的记录了，也就意味着在亿级别的数据中查询一条记录，只需要查询4页，也就是4次IO操作。那么B+树索引的优势是否逐步体现出来了呢？

不过，在真实环境中，每个页其实利用率并没有这么高，还会存在一些碎片的情况。

## 优化B+树索引的插入性能 ##

B+树的查询高效是要付出代价的,也就是在插入时会带来性能问题。

B+ 树在插入时就对要对数据进行排序，但排序的开销其实并没有你想象得那么大，因为排序是CPU操作（当前一个时钟周期CPU能处理上亿指令）。

真正的开销在于B+树索引的维护，保证数据排序，这里存在两种不同数据类型的插入情况。

*  数据顺序（或逆序）插入： B+ 树索引的维护代价非常小，叶子节点都是从左往右进行插入，比较典型的是自增 ID 的插入、时间的插入（若在自增 ID 上创建索引，时间列上创建索引，则 B+ 树插入通常是比较快的）。
 *  数据无序插入： B+ 树为了维护排序，需要对页进行分裂、旋转等开销较大的操作，另外，即便对于固态硬盘，随机写的性能也不如顺序写，所以磁盘性能也会收到较大影响。比较典型的是用户昵称，每个用户注册时，昵称是随意取的，若在昵称上创建索引，插入是无序的，索引维护需要的开销会比较大。

你不可能要求所有插入的数据都是有序的，因为索引的本身就是用于数据的排序，插入数据都已经是排序的，那么你就不需要B+树索引进行数据查询了。

所以对于B+树索引，在 MySQL 数据库设计中，仅要求主键的索引设计为顺序，比如使用自增，而不用无序值做主键。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70]: /images/20220829/8dabf0ff663746ba9dceebd6ac919cb4.png
[662676eb5c4d4470a7547d781a09de9f.png]: /images/20220829/51145cb8c3d842ce971cb86d8059068d.png
[a98cfa326e19494aa1be84f3afe060ca.png]: /images/20220829/5eb30ab62153437eaaeee7db790513f2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 1]: /images/20220829/cd8b148403ac44ed81c1e548348eabca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 2]: /images/20220829/de6b20468b4b4c80837203a4b377e077.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 3]: /images/20220829/e71522569e1a43c1b8264ca0d553e965.png