PostgreSQL 索引物理布局

Question

我想了解 PostgreSQL 物理索引布局是怎样的。我了解到索引是作为具有 B 树数据结构的页面集的一部分存储的。我试图了解吸尘如何影响索引。它有助于控制其尺寸吗？

Answer 1

B 树索引是已有十年历史的技术，因此网络搜索会找到大量详细的详细描述。简而言之：

B 树是索引页（PostgreSQL 中为 8KB）的平衡树，也就是说，树的每个分支都具有相同的深度。 树通常是颠倒绘制的，起始（顶部）节点是根节点，底部的页面称为叶节点。 树的每个level划分搜索空间；级别越深，分区越精细，直到到达叶节点中的各个索引条目。 索引页中的每个条目都指向一个表条目（在叶节点中）或指向下一级的另一个索引页。

这是深度为三的索引的草图，但请注意以下几点：

• 省略了一些节点，实际上所有叶节点都在第3层
• 实际上，一个节点中不是三个条目（keys），而是大约 100 个

 

                                     ┌───────────┐
                level 1 (root node)  │ 20 75 100 │
                                     └───────────┘
                                   ╱    ╱   │     ╲
                                  ╱    ╱    │      ╲
                                 ╱    ╱     │       ╲
                    ┌───────────┐┌─────┐┌──────────┐┌─────┐
           level 2  │ 5  10  15 ││ ... ││ 80 87 95 ││ ... │
                    └───────────┘└─────┘└──────────┘└─────┘
                                       ╱   ╱   │    ╲
                                      ╱   ╱    │     ╲
                                     ╱   ╱     │      ╲
                             ┌─────┐┌─────┐┌──────────┐┌─────┐
        level 3 (leaf nodes) │ ... ││ ... ││ 89 91 92 ││ ... │
                             └─────┘└─────┘└──────────┘└─────┘

一些注意事项：

• 指向下一级的指针实际上位于条目之间的间隙中，在索引中搜索就像“向下钻取”到正确的叶页。
• 每个节点还与其兄弟节点链接，以方便节点的插入和删除。
• 当一个节点已满时，它会分裂为两个新节点。这种分裂可以向上递归，甚至到达根节点。当根节点分裂时，索引深度增加1。
• 现实生活中，B树索引的深度很难超过5。
• 删除索引条目后，会留下空白空间。有一些技术可以通过加入页面来巩固这一点，但这很棘手，而 PostgreSQL 不这样做。

现在回答你的问题：

当表（堆）条目被

VACUUM

删除时，因为它对于任何活动快照都不可见，索引中的相应条目也会被删除。这会导致索引中出现空白空间，可供将来的索引条目重用。

空索引页可以删除，但索引深度永远不会减少。因此，大规模删除可以（在

VACUUM

完成其工作之后）减少索引大小，但更有可能导致臃肿的索引，其中页面仅包含很少的键和大量的空白空间。

一定量的索引膨胀（最多超过 50%）是正常的，但如果大量更新和删除等不寻常的使用模式导致严重的索引膨胀，则必须使用

REINDEX

重写索引，从而摆脱膨胀。此操作会锁定索引，以便所有并发访问都被阻止，直到完成为止。如果这是一个问题，您可以使用

REINDEX ... CONCURRENTLY

，它不需要持久的重锁，但需要更长的时间才能完成。