B+树与索引

B+树与数据库索引

MySQL InnoDB引擎中，使用了B+树的索引模型，数据都是存储在B+树中的，每一个索引在InnoDB中都是一棵B+树。本文首先介绍B+树的概念，然后介绍MySQL的索引。

B+树

数据库引擎有很多可用的数据结构，如哈希表、有序数组、二叉树搜索树。

• 哈希表：键值对，把值放在数组中，用一个哈希函数把key换算成一个确定的位置，然后把value放在数组的这个位置，如果有哈希冲突，其中一种解决方法是链表。哈希表只适用于等值查询的场景。
• 有序数组：按顺序存储，查询用二分法可以快速查询，但是更新效率低，只适用于静态存储引擎。
• 二叉树搜索树：每个节点的左儿子小于父节点，父节点小于右儿子，查询和更新时间复杂度都是O(logN)。

在上述三种数据结构中，只有二叉搜索树能够适用的场景更多，但是直接通过二叉搜索树也不太适合数据库存储，因为二叉搜索树的树高太高，而每一层的数据不太可能存在连续的数据块中，因此一次查询需要访问的数据块太多，尤其是在数据库可能存在磁盘中，速度就更慢了，所以一般都采用“N叉”树。InnoDB采用的是B+树结构，因为B+树能够很好地配合磁盘的读写特性，减少单词查询的磁盘访问次数。

B+树的查询效率更加稳定：由于非终节点并不是最终指向文件内容的节点，而只是叶子节点中关键字的索引。所以任何关键字的查找必须走一条从根节点到叶子节点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

数据库索引

数据库索引用于提高数据查询效率，索引类型分为主键索引和非主键索引（普通索引）：

• 主键索引的叶子节点存的是整行数据；

• 非主键索引的叶子节点内容是主键的值，所以非主键索引也被称为二级索引，通过普通索引查询时，需要先搜索非主键索引树，找到主键，然后再到主键索引树中再搜索一次，这个过程称为回表。基于非主键索引的查询需要多扫描一棵索引树，因此在应用中应该尽量使用主键索引。如果不通过索引来查询，就是遍历主键索引树，因此效率是最低的。

优化数据库索引的一些方法：

• 覆盖索引：假设有一张表，主键是ID，还有一个字段k，并且对k建立了一个非主键索引，在执行select ID from T where k between 3 and 5语句时，因为只需要查询主键ID的值，而主键ID是非主键索引k的叶子节点的值，因此索引k已经“覆盖了”我们的查询需求，不需要回表过程，这就被称为覆盖索引。
• 前缀索引：B+树这种索引结构，可以利用索引的“最左前缀”来定位记录。对于联合索引的最左N个字段或者字符串索引最左M个字符，都可以利用索引来加速检索。
• 索引下推：索引下推指的是可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。