postgresql - GiST 索引中的索引元组与用户表行之间的关系是多对一还是一对一？

Question

在常规的 b-tree 索引中，叶节点包含一个键和一个指向 heap 元组(用户表行)的指针，这表示在 b-tree，索引元组和用户表行是一对一的关系。

就像在 b-tree 中一样，GiST 叶节点也包含一个关键数据和有关 heap 元组存储位置的信息，但是 GiST 叶子可能包含也可能不包含其键中的整行数据(如果我错了请纠正我)。那么，如果我能够将我的表数据的一部分存储在一个叶节点中，另一部分存储在另一个叶节点中，并使它们都指向一个堆元组，是否可能？这将使 GiST 索引元组和 heap 元组之间的关系多对一。

这一切都正确吗？

Answer 1

GiST 索引是 B 树索引的推广。

在B 树索引 的非叶 block 中，两个连续的索引条目定义了这些索引条目之间的指针目的地子树中索引值的边界:

换句话说，每个指向下一个较低级别的指针都标有一个包含子树中所有值的区间。

这仅适用于具有 total ordering 的数据类型.

GiST 索引扩展了该概念。非叶节点中的每个条目都有一个条件，该索引条目下的子树必须满足该条件。

扫描 GiST 索引时，我会在索引页面中搜索所有可能包含与我的搜索条件匹配的值的条目。由于没有总排序，条件有可能(但当然不可取)以某种方式“重叠”，以便我搜索的内容可以在多个条目中匹配。在那种情况下，我必须下降到所有引用的子树，但我可以跳过那些条目条件保证子树不能包含与我的搜索条件匹配的条目的条目。

这有点抽象，所以让我们用一个例子来充实它。

GiST 索引的一个经典示例是 R-tree 索引，这是一种类似于 PostGIS 使用的地理索引:

这里索引条目的条件是一个边界框，它包含索引条目的子树中包含的所有几何图形的边界框。因此，在搜索几何图形时，我会获取其边界框并查看页面中的哪些索引条目包含此边界框。这些是我必须下降到的子树。

在这个例子中可以看到的一件事是 GiST 索引可以是有损，也就是说，它给了我一个neccesary，但不是足够的 如果我找到了命中条件。如果实际表条目也满足条件(并非每个几何图形都是矩形)，则始终必须重新检查在 GiST 索引扫描中找到的叶条目。这就是为什么 GiST 索引扫描在 PostgreSQL 中总是位图索引扫描。

这一切听起来既美好又简单。一个好的 GiST 索引的困难部分是 picksplit 算法，它决定索引页拆分时哪个索引条目进入两个新索引页中的哪个。效果越好，索引的效率就越高。

所以你看，GiST 索引在很多方面“有点像”B 树索引。您可以将 B 树索引视为 GiST 索引的优化特例(参见 btree-gist contrib 模块)。

这让我回答你的问题:

GiST leaf node also contains key datum and info about where the heap tuple is stored

这是真的。

GiST leaves may or may not contain entire row data in its keys

当然索引条目不包含整行。但我认为你的意思是正确的。 GiST 叶子中的条件可以比表中的实际对象更宽，就像边界框比几何体大一样。

if I am able to store one part of my table data in one leaf node and the other part in another leaf node and make both of them point to one heap tuple, would it be possible? This will make the relationship between GiST index tuple and heap tuple many to one.

这是错误的。即使一个值可能满足 GiST 索引页中的多个条目，它也只包含在一个子树中，并且只有一个叶页条目指向任何给定的表行。它是一对一的关系，就像在 B 树索引中一样。