MySQL为什么选择B+树作为索引结构.org

MySQL为什么选择B+树作为索引结构?

背景

MySQL 跟 B+ 树没有直接的关系，真正与 B+ 树有关系的是 MySQL 的默认存储引擎 InnoDB，MySQL 中存储引擎的主要作用是负责数据的存储和提取，除了 InnoDB 之外，MySQL 中也支持 MyISAM 作为表的底层存储引擎。

本文写的问题其实还是，为什么 MySQL 默认的存储引擎 InnoDB 会使用 B+ 树来存储数据，MySQL里无论是表中的数据（主键索引）还是辅助索引最终都会使用 B+ 树来存储数据，其中前者在表中会以 <id, row> 的方式存储，而后者会以 <index, id> 的方式进行存储，这其实也比较好理解：

• 在主键索引中，id 是主键，我们能够通过 id 找到该行的全部列；
• 在辅助索引中，索引中的几个列构成了键，我们能够通过索引中的列找到 id，如果有需要的话，可以再通过 id 找到当前数据行的全部内容；

对于 InnoDB 来说，所有的数据都是以键值对的方式存储的，主键索引和辅助索引在存储数据时会将 id 和 index 作为键，将所有列和 id 作为键对应的值。

既然是选择，肯定有其他假想敌，因为如果我们只有一个选择，那么选择 B+ 树也并不值得讨论，其他选项有二叉查找树（BST）、平衡二叉树（AVT）、红黑树、B树和哈希。我们就以这些数据结构为例，分析比较 B+ 树的优点。

假想敌分析

为什么不使用二叉查找树

二叉查找树(BST，Binary Search Tree)，也叫二叉排序树，在二叉树的基础上需要满足：任意节点的左子树上所有节点值不大于根节点的值，任意节点的右子树上所有节点值不小于根节点的值。

当需要快速查找时，将数据存储在BST是一种常见的选择，因为此时查询时间取决于树高，平均时间复杂度是O(logn)。然而，BST可能长歪而变得不平衡，此时BST退化为链表，时间复杂度退化为O(n)。

总结来说，不具有平衡性，性能差。

为什么不使用平衡二叉树

AVL树是严格的平衡二叉树，所有节点的左右子树高度差不能超过1；AVL树查找、插入和删除在平均和最坏情况下都是O(logn)。

AVL实现平衡的关键在于旋转操作：插入和删除可能破坏二叉树的平衡，此时需要通过一次或多次树旋转来重新平衡这个树。当插入数据时，最多只需要1次旋转(单旋转或双旋转)；但是当删除数据时，会导致树失衡，AVL需要维护从被删除节点到根节点这条路径上所有节点的平衡，旋转的量级为O(logn)。

总结来说，由于旋转的耗时，AVL树在删除数据时效率很低；在删除操作较多时，维护平衡所需的代价可能高于其带来的好处。

为什么不使用红黑树

与AVL树相比，红黑树并不追求严格的平衡，而是大致的平衡：只是确保从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。

与AVL树相比，红黑树的查询效率会有所下降，这是因为树的平衡性变差，高度更高。但红黑树的删除效率大大提高了，因为红黑树同时引入了颜色，当插入或删除数据时，只需要进行O(1)次数的旋转以及变色就能保证基本的平衡，不需要像AVL树进行O(logn)次数的旋转。总的来说，红黑树的统计性能高于AVL。

因此，在实际应用中，AVL树的使用相对较少，而红黑树的使用非常广泛。例如，Java中的TreeMap使用红黑树存储排序键值对；Java8中的HashMap使用链表+红黑树解决哈希冲突问题(当冲突节点较少时，使用链表，当冲突节点较多时，使用红黑树)。

对于数据在内存中的情况（如上述的TreeMap和HashMap），红黑树的表现是非常优异的。但是对于数据在磁盘等辅助存储设备中的情况（如MySQL等数据库），红黑树并不擅长，因为红黑树长得还是太高了。当数据在磁盘中时，磁盘IO会成为最大的性能瓶颈，设计的目标应该是尽量减少IO次数；而树的高度越高，增删改查所需要的IO次数也越多，会严重影响性能。

总结来说，如果使用红黑树，会使树的高度更高，增加IO消耗。

B树与B+树

B树，是为磁盘等辅存设备设计的多路平衡查找树，与二叉树相比，B树的每个非叶节点可以有多个子树。因此，当总节点数量相同时，B树的高度远远小于AVL树和红黑树(B树是一颗“矮胖子”)，磁盘IO次数大大减少。

B+树是B树的变种，B树和B+树在数据结构上其实有一些类似，它们都可以按照某些顺序对索引中的内容进行遍历，对于排序和范围查询等操作有很好的性能。

B树与B+树的最大区别就是，B树可以在非叶结点中存储数据，但是B+树的所有数据其实都存储在叶子节点中。这里所说的数据，可能是行的全部数据（如Innodb的聚簇索引），也可能只是行的主键（如Innodb的辅助索引），或者是行所在的地址（如MyIsam的非聚簇索引）。

B+树的叶节点之间通过双向链表链接。

总结来说，选择B+树而不是B树的原因：B树能够在非叶节点中存储数据，但是这也导致在查询连续数据时可能会带来更多的随机I/O，而B+树的所有叶节点可以通过指针相互连接，能够减少顺序遍历时产生的额外随机I/O。

为什么不使用哈希表

哈希作为底层的数据结构的表能够以O(1)的速度处理单个数据行的增删改查，但是面对范围查询或者排序时就会导致全表扫描的结果。

总结来说，哈希表对于范围查找和排序效率低，但对于单个数据的查询效率很高。

总结

MySQL选择B+树作为索引结构的原因主要是下面的两个方面:

• MySQL需要支持的场景和功能需要在特定查询上拥有较强的性能；
• CPU将磁盘上的数据加载到内存中需要花费大量的时间，这使得B+树成为了非常好的选择；

数据的持久化以及持久化数据的查询其实是一个常见的需求，而数据的持久化就需要我们与磁盘、内存和CPU打交道；MySQL作为OLTP的数据库不仅需要具备事务的处理能力，而且要保证数据的持久化并且能够有一定的实时数据查询能力，这些需求共同决定了B+树的选择。