mysql - B+树的聚簇索引和非聚簇索引保存在哪里？

Question

目前我正在阅读有关B+ Tree 的基础知识，并对聚簇索引和非聚簇索引的空间分配感到困惑。

当我们在B+ 树 上创建聚簇索引时，索引存储在主内存中，叶子包含指向实际 block 的数据指针。 block 存储在磁盘中， block 包含记录。

• 通常聚簇索引是在主键上创建的
• 只能有一个聚簇索引

现在假设我们有一个表 (id, name, class)，我在 name 和 class 上创建了两个非聚集索引。 我怀疑非聚集索引将存储在哪里？以及如何搜索像

这样的 query

select id, name, class from table where id = 3, name='Leo' and class='10'

我的假设:

• 因为 id 字段是主键所以首先使用聚集索引将 id = 3
• 现在使用name 和class 上的非聚集索引，我们将找到剩余的字段

你觉得我的假设对吗？您能否详细说明有关存储聚集索引的信息？ 这两个索引(聚集和非聚集形成 n 叉树吗？)。我无法同时显示聚簇索引和非聚簇索引。

Answer 1

我说的是 InnoDB...

PRIMARY KEY(如您所说)与数据聚类。整个 BTree(数据 + PK)存储在磁盘上的一组 block 中(不是“主内存”)。 “叶”节点包含所有列。

辅助键是一个单独的 BTree。在结构上，除了叶节点中的内容外，这两个 BTree 是相同的。对于辅助键，将 PRIMARY KEY 的副本放入叶节点。因此，当使用二级索引查找一行(“点查询”)时，有两个 BTree 向下钻取 - 一个用于二级索引，一个用于 PK。

所有 block 都“缓存”在“buffer_pool”中，因此它们有时在主内存中，但总是(迟早)保留在磁盘上。 (事务日志等)确保“稍后”不违反数据始终存在的规则。)

你的两张照片是一个不错的开始。然而……

• 非叶节点链接在一起(如您所示)，但它们不一定在磁盘上相邻。插入新行(或新索引条目)时， block 可能会因为已满而“ split ”。这导致 block 散布在磁盘周围。
• 叶节点也连接在一起，但可以分散。
• 对于Unclustered，嗯，建议你重新开始，考虑PK问题等。

您需要了解比图片试图传达的更高层次的信息:

• 点查询下钻btree
• 二次查找必须进行 2 次向下钻取
• “范围”扫描——数据或索引——非常有效，因为它们扫描一个 block ，然后通过底层 block 之间的双向链接移动到(逻辑上)下一个 block .因此，它实际上是一个 B+Tree，而不仅仅是一个 BTree。
• (更多关于范围)WHERE clustered_key BETWEEN ... 非常有效
• (更多关于范围)WHERE secondary_key BETWEEN ... 在找到所需的 PK 值方面非常有效，但随后会变成一堆(可能)随机点查询。
• 所有 block 在缓存方面几乎都是等价的。但是(显然？)由于“最近最少使用”算法，非叶节点倾向于存在于缓存中。 (我省略了很多细节。)
• 只能有一个聚簇索引。 (除非您愿意复制所有数据。这已在 InnoDB 以外的几个引擎中完成。)
• 一个 block 包含尽可能多的“记录”(数据或索引或非叶)，从 1 到数百不等。
• 默认情况下，一个 block 为 16KB。 (而且不容易改变。)
• 使用 innodb_file_per_table=ON，给定表的所有 BTree 都位于单个 .ibd“表空间”中。
• 在 innodb_file_per_table=OFF 的情况下，所有表的所有 BTree 都位于一个名为 ibdata1 的全局“表空间”中。 (同样，过于简单化了。)

现在对于 MyISAM:

• 一个表的数据保存在一个文件 (.MYD) 中。
• 一个表的所有索引(包括 PRIMARY KEY)都在一个文件 (.MYI) 中
• 所有索引都是 B 树。 (数据不是。)
• 索引“指向”数据文件的叶节点。
• 索引 block 为 1KB。
• 数据文件只是一个随机访问流。

(还有很多细节。)