Postgres使用btree索引与MySQL B +树

Question

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

当我试图确定两个系统使用多少空间时,我发现表的差异要小得多,但发现索引存在巨大差异.

MySQL索引比表数据本身占用更多的大小,而postgres使用的是相当小的大小.

• 在挖掘原因时,我发现MySQL使用B +树来存储索引,而postgres 使用 B树.

• MySQL的索引使用情况略有不同,它将数据与索引一起存储(由于增加的大小),但postgres没有.

现在的问题是:

• 比较数据库上的B树和B +树,最好使用B +树,因为它们更适合范围查询O(m)+ O(logN) - 其中范围中的m和B +树中的查找是对数的吗？

  现在在B树中,对于范围查询,查找是对数的,因为它没有数据节点的链接列表底层结构,所以它会射到O(N).话虽如此,为什么postgres使用B树？它是否适用于范围查询(确实如此,但它如何在内部处理B树)？

• 上面的问题来自postgres的观点,但从MySQL的角度来看,为什么它比postgres使用更多的存储,在现实中使用B +树的性能优势是什么？

我本可以错过/误解很多事情,所以请随时纠正我的理解.

编辑回答Rick James的问题

• 我正在使用InnoDB引擎用于MySQL
• 我在填充数据后构建了索引 - 就像我在postgres中所做的那样
• 索引不是UNIQUE索引,只是普通索引
• 没有随机插入,我在postgres和MySQL中都使用了csv加载,只有在此之后我创建了索引.
• 索引和数据的Postgres块大小是8KB,我不确定MySQL,但我没有改变它,所以它必须是默认值.
• 我不会把行称为大,他们有大约4个文本字段,长度为200个字符,4个十进制字段和2个bigint字段 - 19个数字长.
• PK是一个包含19个数字的bigint列,我不确定它是否笨重？在什么尺度上应区分笨重而非笨重？
• MySQL表大小为600 MB,Postgres大约310 MB,包括索引 - 如果我的数学运算正确,这相当于大48%的大小.但是有没有办法可以在MySQL中单独测量索引大小,不包括表大小？这可能会导致更好的数字.
• 机器信息:我有足够的RAM - 256GB以适应所有的表和索引,但我认为我们根本不需要遍历这条路线,我没有看到它们两个都有明显的性能差异.

其他问题

• 当我们说碎片发生？有没有办法去碎片化,以便我们可以说除此之外,没有什么可做的.顺便说一句,我正在使用Cent OS.
• 有没有办法在MySQL中测量索引大小,忽略主键,因为它是聚类的,这样我们实际上可以看到什么类型占用更大的大小(如果有的话).

Answer 1

首先,如果您不使用InnoDB,请关闭此问题,使用InnoDB重建,然后查看是否需要重新打开问题.MyISAM 不是首选,不应讨论.

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

MySQL:数据和索引存储在由16KB块组成的B +树中.

MySQL: UNIQUE在插入行时必须更新索引(包括PRIMARY KEY).因此,索引必然会有很多块拆分等.UNIQUE

MySQL:它与数据PRIMARY KEY聚集在一起,所以它实际上占用了零空间.如果以PK顺序加载数据,则块碎片最小.

非UNIQUE辅助密钥可以在运行中构建,这导致一些碎片.或者可以在加载表之后构造它们; 这导致更密集的包装.

辅助密钥(UNIQUE或不包含)隐含地包含PRIMARY KEY在其中.如果PK是"大"那么辅助键是庞大的.你的PK是什么？这是'答案'吗？

理论上,完全随机插入BTree导致块大约69%满.也许这就是答案.MySQL是否大45%(1/69%)？

对于100M行,可能有许多操作受I/O限制,因为您没有足够的RAM来缓存所需的所有数据和/或索引块.如果所有内容都被缓存,那么B-Tree与B + Tree将没有太大区别.让我们分析一些范围查询在未完全缓存的情况下需要发生什么.

对于任一类型的树,操作都从树中的向下钻取开始.对于MySQL,100M行将具有大约4级深度的B +树.3个非叶节点(同样是16KB块)将被缓存(如果它们还没有)并被重用.即使对于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,二级索引的低效构建,大行,块大小......)

关于PRIMARY KEY的补遗

对于InnoDB,需要注意的另一件事是:PRIMARY KEY在加载数据之前最好在表的定义中使用.最好先按PK顺序对数据进行排序LOAD DATA.没有指定任何PRIMARY KEY或UNIQUE密钥,InnoDB构建一个隐藏的6字节PK; 这通常是次优的.

Answer 2

在数据库中，您经常会查询谁提供了一些数据范围，例如 id 从 100 到 200 的数据。
在这种情况下

• B-Tree 需要遵循从根到叶子的路径，为每个条目获取数据指针。
• B+-树可以“行走”穿过叶子，并且仅在第一次时必须沿着到达叶子的路径（即对于 id 100）

这是因为B+-Tree只在叶子中存储数据（或数据指针），并且叶子是链接的，以便您可以执行快速的有序遍历。

B+树

另一点是：
在 B+Tree 中，内部节点仅存储指向其他节点的指针，而没有任何数据指针，因此您有更多的指针空间，并且需要更少的 IO 操作，并且可以在内存页中存储更多节点指针。

因此，对于范围查询，B+ 树是最佳的数据结构。对于单一选择，B 树可能更好（由于树的深度/大小），因为数据指针也位于树内部。