MySQL中为什么选用了 B+ 树

发表于： 分类于：
字数： 2035 阅读：≈ 5分钟 浏览：

MySQL的索引是一种数据结构，用于加快数据库查询的速度和性能。它通过在数据表列上创建索引结构（如B+Tree、Hash索引等），加速查询速度。

这是一种用空间换时间的做法。

我们学习数据结构的时候，是从简单到复杂的。「二叉树」这种数据结构也是如此：

  • 二叉查找树(BST)：解决了排序的基本问题，就是一个排序的二叉树，但是由于无法保证平衡，可能退化为链表；
  • 平衡二叉树(AVL)：通过旋转解决了平衡的问题，但是旋转操作效率太低，为了达到平衡要旋转很多次，费时间。
  • 红黑树：通过舍弃严格的平衡和引入红黑节点，解决了AVL旋转效率过低的问题，可以只旋转一次完成新增和删除，但是在磁盘等场景下，树仍然太高，IO次数太多。
  • B树：通过将二叉树改为多路平衡查找树，解决了树过高的问题，所以 B 树是一棵「矮胖子」
  • B+树：在B树的基础上，将非叶节点改造为不存储数据的纯索引节点，进一步降低了树的高度；此外将叶节点使用指针连接成链表，范围查询更加高效。

红黑树

  • 红黑树并不追求严格的平衡，而是大致的平衡。
  • 当插入或删除数据时，只需要进行O(1)次数的旋转以及变色就能保证基本的平衡，不需要像AVL树进行O(lgn)次数的旋转
  • 对于数据在内存中的情况（比如 Java 中的 TreeMap、HashMap），在 JDK8 中就用了红黑树。
  • 对于数据在磁盘等辅助存储设备中的情况（如MySQL等数据库），红黑树还是太高。当数据在磁盘中时，磁盘IO会成为最大的性能瓶颈，设计的目标应该是尽量减少IO次数；而树的高度越高，增删改查所需要的IO次数也越多，会影响性能。

B 树

B树也称B-树，是为磁盘等辅存设备设计的「多路平衡查找树」。与二叉树相比，B树的每个非叶节点可以有多个子树。

当总节点数量相同时，B树的高度远远小于 AVL 树和红黑树，磁盘IO次数大大减少。

定义B树最重要的概念是阶数(Order)，主要是对非叶结点的子节点数量和记录数量的限制。

mongodb的索引使用了B树结构。

局部性原理

当一个数据被使用时，其附近的数据有较大概率在短时间内被使用。B树将键相近的数据存储在同一个节点，当访问其中某个数据时，数据库会将该整个节点读到缓存中；当它临近的数据紧接着被访问时，可以直接在缓存中读取，无需进行磁盘IO，也就是说，B树的缓存命中率更高。

B+ 树

B+树也是多路平衡查找树，是为了数据库查找而生的，是 B 树的变种。

区别：

  • B树中每个节点（包括叶节点和非叶节点）都存储真实的数据
  • B+树中只有叶子节点存储真实的数据，非叶节点只存储键（索引数据，放数据的话，太占位置了）
  • B树中一条记录只会出现一次，不会重复出现
  • B+树的键则可能重复重现，一定会在叶节点出现，也可能在非叶节点重复出现。
  • B+树的叶节点之间通过双向链表链接，B 树没有。这链表就是为了「范围查询」

在 MySQL 中，真实数据的划分有：

  • 行的全部数据（如Innodb的聚簇索引），也就是非叶子节点就是id，查到叶子节点就是一串业务数据字段了。
  • 主键（如Innodb的辅助索引），非叶子节点是索引，查到叶子节点是id。

B+树的优势

更少的IO次数：B+树的非叶节点只包含键，不包含真实数据，因此每个节点存储的记录个数比B数多很多（即阶m更大），因此B+树的高度更低，访问时所需要的IO次数更少。此外，由于每个节点存储的记录数更多，所以对访问局部性原理的利用更好，缓存命中率更高。

更适于范围查询：在B树中进行范围查询时，首先找到要查找的下限，然后对B树进行中序遍历，直到找到查找的上限；而B+树的范围查询，只需要对链表进行遍历即可。

更稳定的查询效率：B树的查询时间复杂度在1到树高之间(分别对应记录在根节点和叶节点)，而B+树的查询复杂度则稳定为树高，因为所有数据都在叶节点。

B+树高和数据量估算

树的高度一般在2-4层。

  • 树的高度是由阶数决定的，阶数越大树越矮；
  • 阶数的大小：取决于每个节点可以存储多少条记录。
  • Innodb中每个节点使用一个页(page)，页的大小为16KB，其中元数据只占大约128字节左右(包括文件管理头信息、页面头信息等等)，大多数空间都用来存储数据。

非叶子节点：

记录包含索引的键、指向下一层节点的指针。

当索引是整型或较短的字符串时，一条记录占用的大小是 16 字节（byte），记录数 = 16kb / 16byte 约等于 1000

所以，我们说索引的列长度不应该太长，比如 MySQL < 5.7的时候，单字节最大索引长度是 767byte，因为索引长度大则page放的数量少了，树就高了，索引效果就差，还浪费空间。

叶子节点：

记录包含了索引的键和值，数据量更大，假设叶子节点数据量为 100 个。如果是聚簇索引，数据量大，则可能小于 100，如果是普通索引，就放个id的话，就远超 100 个。

所以，如果我们有非常大的字段，比如存放了图片的base64，存放了富文本数据等单个大字段，可以另外建一张表来 left join 连接一下。

对于一颗3层B+树，第一层 1 个节点，存放 1000 个，第二层就是 1000 * 1000，第三层就是 1000 * 1000 * 100 = 1 亿条。

已经够多了，我们实际上到 1000W 条数据的时候，就考虑分库分表了。