0

我试图了解 PostgreSQL 物理索引布局是如何的。我开始知道索引是作为具有 B 树数据结构的页面集的一部分存储的。我试图了解吸尘如何影响索引。它有助于控制它的大小吗？

4

1 回答 1

4

B-tree 索引是有十年历史的技术，所以网络搜索会找到很多很好的详细描述。简而言之：

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

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

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

 

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

一些注意事项：

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

现在回答你的问题：

当一个表（堆）条目VACUUM因为对任何活动快照不可见而被删除时，索引中的相应条目也会被删除。这会导致索引中出现空白空间，这些空间可以被未来的索引条目重用。

空的索引页可以删除，但索引的深度永远不会减少。因此，大规模删除可以（在VACUUM完成其工作之后）减小索引大小，但更有可能导致索引膨胀，其中的页面仅包含少量键和大量空白空间。

一定程度的索引膨胀（高达 50% 以上）是正常的，但如果不寻常的使用模式（如大量更新和删除）导致不良索引膨胀，则必须使用 重写索引REINDEX，从而消除膨胀。不幸的是，此操作锁定了索引，因此所有并发访问都被阻塞，直到完成为止。

于 2017-03-16T09:43:52.870 回答