btree索引与MySQL B+trees的后置使用

Question

我们正在从MySQL迁移到PGSQL，我们有一个1亿行表。

当我试图确定两个系统使用多少空间时，我发现表的差异要小得多，但是索引的差异很大。

MySQL索引占用比表数据本身更大的大小，而postgres使用的大小要小得多。

• 在挖掘原因时，我发现MySQL使用B+树来存储索引和postgres uses B-树。
• MySQL对索引的使用略有不同，它与索引一起存储数据(由于索引的大小增加)，但postgres没有。

现在的问题是：

• 比较数据库上的B树和B+树，使用B+trees更好，因为它们更适合于范围查询O(m) + O(logN) -其中m在范围内，查找在B+trees中是对数的？ 现在，在B-树中，对范围查询的查找是对数的，因为它没有数据节点的链接列表底层结构，所以它的范围查询上升到O(N)。话虽如此，为什么postgres会使用B树呢？对于范围查询，它执行得好吗(确实如此，但是它如何在内部处理B树)？
• 上面的问题是从postgres的角度来看，但是从MySQL的角度来看，为什么它比postgres使用更多的存储空间，在现实中使用B+trees的性能好处是什么？

我可能错过了/误解了很多事情，所以请随时纠正我在这里的理解。

编辑回答里克·詹姆斯的问题

• 我使用InnoDB引擎实现MySQL
• 我在填充数据之后构建了索引，就像在postgres中一样。
• 这些索引不是唯一的索引，只是普通的索引。
• 没有随机插入，我在postgres和MySQL中都使用了csv加载，然后创建了索引。
• Postgres索引和数据的块大小都是8KB，我不确定MySQL的大小，但是我没有更改它，所以它必须是默认值。
• 我不认为行很大，它们大约有4个文本字段，200个字符长，4个十进制字段和2个bigint字段--19个数字长。
• P.K是一个有19个数字的bigint列，我不确定这是否很大？在什么尺度上应该区分笨重和非笨重？
• MySQL表的大小是600 MB，Postgres大约是310 MB，包括索引--如果我的数学是right.But，那么这相当于48%的大小，有什么方法可以在MySQL中单独测量索引大小(不包括表大小)？我想这能带来更好的数字。
• 机器信息:我有足够的RAM -256 of来把所有的表和索引放在一起，但是我认为我们根本不需要遍历这个路径，我没有看到它们在性能上有任何明显的差别。

附加问题

• 当我们说碎裂发生的时候？有没有办法去分割，这样我们就可以说，除此之外，没有什么可做的，顺便说一句，我使用的是分操作系统。
• 是否有一种方法可以在MySQL中测量索引大小，而忽略聚集时的主键，这样我们就可以实际看到哪些类型占用了更大的大小(如果有)。

Answer 1

首先，如果您没有使用 InnoDB ，请关闭此问题，用InnoDB重新构建，然后查看是否需要重新打开该问题。MyISAM是不可取的，不应该讨论。

是如何在MySQL中构建索引的？有几种方法可以显式或隐式地构建索引；它们会导致更好或更糟糕的打包。

MySQL:数据和索引存储在由16 in 块组成的B+Trees中。

MySQL:在插入行时，必须更新UNIQUE索引(包括PRIMARY KEY) 。因此，一个UNIQUE索引必然会有很多块分裂，等等。

PRIMARY KEY 是与数据聚集在一起的，因此它实际上占用了零空间。如果您按PK顺序加载数据，那么块碎片是最小的。

非UNIQUE辅助键可以动态构建，这会导致一些碎片.或者，它们可以在加载表后构建；这将导致更密集的包装。

辅助键(UNIQUE或not)隐式地包括它们中的PRIMARY KEY。如果PK是“大”的，那么辅助键是笨重的。你的PK是什么？这就是“答案”吗？

理论上，在BTree中完全随机插入将导致块约为69%的完全。也许这就是答案。MySQL是否大于45% (1/69%)？

有了1亿行，许多操作可能是I/O绑定的，因为您没有足够的RAM来缓存所需的所有数据和/或索引块。如果所有的东西都是缓存的，那么B树和B+Tree不会有太大的区别。让我们分析在没有完全缓存的情况下，范围查询需要发生什么。

无论哪种类型的树，操作都从树中的向下钻取开始.对于MySQL，1亿行将具有大约4层深度的B+Tree。3个非叶节点(同样是16 if块)将被缓存(如果它们还没有缓存)并被重用。即使对于Postgres，这种缓存也可能发生。(我不认识Postgres。)然后开始范围扫描。使用MySQL，它遍历块的其余部分。(经验法则:一块100行。)对Postgres来说也是？

在街区的尽头，一定会发生一些不同的事情。对于MySQL，有一个指向下一个块的链接。这个块(多100行)是从磁盘(如果没有缓存的话)获取的。对于B树，需要再次遍历非叶节点。2，可能还有3个级别被缓存。我预计需要从磁盘中只从1/10K行获取另一个非叶节点。(10K = 100*100)也就是说，即使在“冷”系统中，Postgres击中磁盘的频率也可能比MySQL高1%。

另一方面，如果行太胖，只有1或2行可以容纳16K块，我一直使用的"100“更像是"2"，1%可能变成50%。也就是说，--如果您有大行--这可能是“答案”。是吗?

，Postgres中的块大小是多少？注意到，上面的许多计算都取决于块和数据之间的相对大小。这会是一个答案吗？

结论：，我已经给出了4个可能的答案。你是否愿意补充这个问题，以证实或反驳每一个问题的适用？(次级索引存在，PK大，次级索引生成效率低，行大，块大小.)

关于主键的增编

对InnoDB来说，还有一件事要注意.在加载数据之前，最好在表的定义中有一个PRIMARY KEY。最好在LOAD DATA之前按PK顺序对数据进行排序。在不指定任何PRIMARY KEY或UNIQUE键的情况下，InnoDB构建一个隐藏的6字节PK；这通常是次优的。

Answer 2

在这里，MySQL和PostgreSQL并不是完全可比的，Innodb使用一个索引来存储表数据(而辅助索引只是指向pkey)。这对于单行pkey查找和B+树都很好，对pkey字段上的范围查询做得很好，但是对于其他所有方面都有性能上的缺点。

PostgreSQL使用堆表并将索引单独放置。它支持许多不同的索引算法。根据您的范围查询，btree索引可能对您没有帮助，您可能需要GiST索引。同样，GIN索引可以很好地用于成员查找(用于数组、fts等)。

我认为使用btree是因为它擅长于简单的用例:什么库包含以下数据？例如，这就成了杜松子酒的一个组成部分。

但是，PostgreSQL不能使用B+树是不正确的。GiST是以广义格式建立在B+树索引之上的。因此，PostgreSQL为您提供了在B+树有用的地方使用它们的选项。