底层数据结构
在 MySQL 索引的底层数据结构为 B+ 树.
为什么是 B+ 树 ?
作为一个数据库, 在我们查询时, 一定要在短时间内返回我们需要的结果, 那我们可以选择的数据结构就基本可以锁定在树这种数据结构中了.
可以使用二叉搜索树吗 ?
如果数据分布均匀的话, 二叉搜索树可以以 O(logN) 的时间复杂度查找到我们需要的数据, 但是如果在插入时是顺序插入的, 那么二叉树就会退化为链表, 因此在这种情况下查找的时间复杂度就会降到 O(N) , 这肯定不是我们期待的等待时间.
可以使用红黑树吗 ?
如果我们使用红黑树这种可以自平衡的二叉搜索树, 可以让我们在顺序插入数据时, 不会出现树退化为链表的情况. 在解决了存储数据随机性的问题后, 我们可以开始考虑存储数据的量级了, 如果我们向数据库中插入了 100w 条数据, 那么红黑树就会有很高的树高, 同时由于红黑树限制了左右子树的层级差不可以超过 1 , 因此由于只有两个分叉, 在插入数据时可能可能会出现多次的自平衡操作.
可以使用 B 树吗 ?
如果我们使用 B 树, 我们可以摆脱每一个树的层级只有两个节点的现状, 使树高可以大幅度的降低, 同时进行自平衡的次数也会减少. 此时, 似乎已经可以满足我们的需求了, 但是 B 树的每一个节点都存储了数据, 因此在我们查询时, 如果只需要使用当前节点作为索引, 那么至此的 磁盘IO 就读入了大量的无用数据, 所以如果每一行的数据较多的话, 还是会有多次 磁盘IO 的问题.
可以使用 B+ 树吗 ?
为了解决上面的问题, B+树 选择把数据都存储在叶子节点当中, 非叶子节点都只存储索引项, 使得在查询时可以减少 磁盘IO 的次数, 同时在对节点进行删除时, 由于存在冗余索引节点, 所以在删除的时候, 很少会出现树的结构变化. 同时在 MySQL 中底层的叶子节点之间还使用了双向链表进行连接.
MyISAM 与 InnoDB 两个引擎之间有什么区别吗 ?
这两个引擎所使用的数据结构都是 B+ 树. 但是与 MyISAM 引擎不同的一点是, 在 InnoDB 引擎中, 数据是存储在主键索引树上的, 而在 MyISAM 引擎中, 索引与数据是分开存储在两个文件中的, 索引中只存储了数据的地址. 因此, 在 InnoDB 引擎中, 主键索引是一定存在的, 如果创建时未指定, 那么 MySQL 会自动添加一个隐藏索引, 这也是 InnoDB 引擎的主键索引也叫聚簇索引的原因.
主键索引与非主键索引之间的区别是什么 ?
之前有提到在主键索引当中存储了数据, 在非主键索引中并不存储数据, 而是存储了主键的值, 在通过非主键索引查询到数据之后还需要去主键索引中查询到指定的数据.
但是也并不是所有的查询都会再次回到主键索引中再次查找一次. 如果使用的是联合索引, 同时查询的字段都处于联合索引的字段当中, 那么就可以直接从联合索引中返回查询结果, 减少一次回表查询; 以及, 即使我们所查询的字段没有被联合索引覆盖, 但是查询条件属于联合索引内, 在 MySQL 8.0 后可以直接在这个阶段使用索引进行判断, 而不是直接回表查询.