Postgres 如何制作它的 B 树索引？

Question

我想估计使用 B 树方法读取 PostgreSQL 部分索引需要多少次，因为我无法直接更改块大小。PostgreSQL关于索引的手册 这里 和 这里 关于块大小，对于 aux 来说是 100，所以有 3 次读取。

块大小占用的默认内存为 8 KB，即通常 1 个块，但我不确定这是否可能，因为 log_1(2) 是无穷大。我的想法是，在 PostgreSQL 中也可能动态计算读取次数 这里 考虑 B 树，其中块大小决定读取次数。我想知道这个块大小是多少： log_b n 在哪里 b 是块大小并且 n 是事件的数量。我认为这在数学上不可能是一个。我认为 Postgres B 树是按照 Wiki 页面中描述的标准方式实现的，Cormen 等人也描述了这一点。

B树索引只包含PostgreSQL中的键，基于此 回答. 。然后数据再次位于逻辑堆表中。索引的目的首先是存储键。数据位于表中，表是逻辑堆，基于 这里。我对PostgresSQL如何创建称为B树的实体感兴趣。基于 这里, ，B 树索引和表的物理存储使用相同的数据页，并且页面布局基本相同。然而，我对这个实体如何协同工作感兴趣。也许，索引和数据的功能可以这样描述：

B 树从根开始生长，而不是从叶子开始。

但更准确地说，来自苏马蒂岛 关系数据库管理系统基础知识（计算智能研究）:

在 B 树中，非叶节点比叶节点大。对数据记录的指针在树的所有级别上都存在。

在B+树中，指针仅存在于叶子处。如何评估 B 树的指针系统？如何描述 PostgreSQL B 树占用的 big-O 空间？Postgres 如何制作它的 B 树索引？

Answer 1

马西，

PostgreSQL B-Tree 索引非常强烈地基于 雷曼和姚实施, ，其中包括大量围绕多版本并发控制的工作，但本文中仍然有很多信息。

当然，PostgreSQL 并没有对论文中的方法进行 100% 准确的复制，要找到差异，除了 (1) 找一个了解 PostgreSQL B-Tree 并且有时间阅读复杂解释的人，或者 (2) 挖掘通过 源代码 你自己。

另一种可能性是您可以访问 Bruce Momjian 的优秀参考网站, ，他在其中更详细地讨论了 PostgreSQL 的内部结构。

然而，在这种情况下，根据你问题的性质，我觉得你可能对 B 树索引的工作原理有一个根本性的误解。在这种情况下，我想进行一些谷歌搜索，或者阅读教科书的一部分，例如 Elmasri 和 Navathe 的数据库系统基础知识 会给你带来一些好处。