MySQL索引的底层数据结构原理剖析(二叉树、 红黑树、Hash、B-Tree、B+Tree)

好吧，我们来谈谈MySQL索引。

B+树索引 MySQL 5 .7 到8 .0默认使用B+Tree。
这个东西有什么特点呢？即数据按顺序放置在叶子节点上，密钥存储在非叶子节点上。
如果要检查col2 =8 9 ，先在非叶子节点查找，找到叶子节点直接查找。
比没有索引好得多。

二叉树索引 你说的是二叉树，很简单。
左边小，右边大。
但当数据量较大时，比如1 00万条记录，二叉树很容易变成链，搜索速度慢。

红黑树索引 红黑树是二叉树的更新版本，保证更加平衡。
但无论数据量有多大，比如1 00万条，高度仍然需要计算。
比如有1 00万条数据，高度可以是2 0级。
每次检查需要2 0次I/O，还是很慢。

B树索引 想一想，红黑树节点只存储一个键+一个地址，太浪费了。
B-Tree 将多个键+地址存储在一个节点中并降低高度。
这就是B+Tree的思想，MySQL默认使用的就是B+Tree。

哈希索引 哈希索引更简单。
只需计算哈希值并将其存储在表中即可。
验证时也直接计算哈希值，比B+Tree更快。
但是，哈希表无法验证范围。
例如，启用列 > 1 0 会混淆哈希。

唯一索引 这意味着索引值必须不同。
例如，具有 UNIQUE 约束的主键或列。
数据库确保该列的值是唯一的。

聚集索引（主键索引） 在聚集索引中，数据本身按索引顺序存储。
例如，如果主键自动递增，则新添加的数据将放在后面，树的划分就会减少。
叶节点存储整行数据。

非聚集索引（辅助索引） 非聚集索引叶节点存储主键值，而不是整行数据。
为什么？节省空间。
一个表有多个非主键索引。
如果它们存储整行数据，则会占用太多空间。
并且要更改数据，只需要更改主键数据，而不需要更改存储在每个索引中的副本。

覆盖指数 如果非聚集索引能够找到你想要的数据，就不需要检查聚集索引，直接从非聚集索引中获取即可。
例如，如果您检查col2 =8 9 ，并且非聚集索引叶节点存储了整行数据，则只需检索它即可。
无需重新运行聚集索引。
这称为覆盖指数，具有很高的性能。

前缀索引 也就是说，索引只存储列值的前几个字符。
例如，“用户名”列中的索引仅存储前 8 个字符。
这样可以节省空间，但您可能需要检查几次。

综合指数 这意味着多个列被组合成一个索引。
例如（col1 ，col2 ）。
查询时，数据库会检查 SQL 条件中使用了哪些列，然后决定使用哪个复合索引。
顺序很重要。

InnoDB 和 MyISAM InnoDB表数据文件本身是一棵B+Tree，可以快速找到数据。
MyISAM 索引和数据文件是分开了。
查询数据需要两步过程。
所以慢慢来吧。

主键自动递增 为什么建议主键自动递增？因为每加1 ，新的数据总是放在后面，树划分得更少。
像UUID这样的乱码可能每次插入都需要重新平衡，速度慢。

总结一下 B+Tree是主流，Hash比较特殊但也有局限性。
覆盖索引可以节省麻烦，将主键存储在非聚集索引中可以节省空间。
复合索引取决于顺序，前缀索引取决于需求。
InnoDB比MyISAM强。

一条 SQL 查询语句如何执行的

我记得有一次，一个周末，我坐在电脑前，准备运行一个 SQL 查询来显示数据库中某个表的数据。
当时我用的是MySQL数据库，查询语句很简单，就是“select from users where id=1 0;”。
我按下 Enter 并等待结果。

结果很快就返回了。
我一看，ID为1 0的用户信息就在眼前。
这让我想起了运行SQL查询的过程。
其实这背后还有很多学问。
首先，连接器建立连接，检查我的权限，并确保我可以访问该表。
那么查询缓存可能已经命中了，但是这次我不记得了，所以继续到解析器。

解析器分析了我的 SQL 语句并识别了关键字、表名和条件。
优化器开始工作，它分析了成本并决定使用ID索引来加速查询。
执行器调用存储引擎（例如InnoDB）来读取数据。
存储引擎找到索引，快速定位到ID为1 0的行，并将结果返回给执行器。

执行器将结果封装成结果集，并通过连接器返回给客户端，也就是我的电脑。
这一切发生得太快了，我几乎感觉不到数据库查询的复杂性。

我有时会想，如果数据库查询的每一步都像这个查询一样简单该多好。
但实际上，每个步骤都可能成为性能瓶颈，需要仔细优化。
例如，如果查询缓存丢失或者表没有合适的索引，查询可能会慢很多。

等等，我突然想到，如果我经常查询这个ID为1 0的用户，是不是可以考虑缓存查询结果，以便下次查询更快？