超过1列的B树索引是什么样的？

Question

所以我正在阅读索引及其实现,我偶然发现了这个简短解释b-tree索引的网站:

b-tree索引对于仅在单个列上的索引非常有意义,但是假设我创建了一个包含多列的索引,那么b-tree如何工作呢？b树中每个节点的价值是多少？

例如,如果我有这个表:

table customer:
id    number
name   varchar
phone_number   varchar
city   varchar

我创建了一个索引:(id,name,city)

然后运行以下查询:

SELECT id, name 
  FROM customer
 WHERE city = 'My City';

该查询如何利用多列索引,或者除非将索引创建为(city,id,name)或(city,name,id),否则它不会使用它？

Answer 1

对于大多数实现,密钥只是一个包含所有键值的较长键,带有分隔符.没有魔法;-)

在您的示例中,键值可能看起来像

"123499|John Doe|Conway, NH"
"32144|Bill Gates| Seattle, WA"

具有复合键的这些索引的特征之一是在某些情况下可以使用中间树节点来"覆盖"查询.

例如,如果查询是查找给定ID的名称和城市,由于ID在索引中是第一个,因此索引可以有效地搜索.一旦进入中间节点,它就可以从密钥"解析"名称和城市,而不需要转到叶子节点来读取它.

但是,如果查询还想显示电话号码,那么当找到完整记录时,逻辑将跟随叶子.

这是一个很好的第一直觉，但实现可能还有更多的问题，例如，数据的类型很重要（数字、可变长度文本和 Postgres 中常见的外来数据），因此任何串联都需要在使用时，需要一些数据字典。仅索引扫描也需要起作用。此外，Oracle 索引组织表是存储整个表（包括非索引列）的 B 树（B* 树）。在所有这些情况下，列数据必须保持分区才能恢复信息。可能的例外：对仅 CHAR 成分进行常规索引扫描 (2认同)

Answer 2

想象一下,密钥由Python元组(col1,col2,col3)表示......索引操作涉及tuple_a与tuple_b...... 进行比较,如果你不知道你感兴趣的col1和col2的哪个值,只是col3,然后它必须读取整个索引("完整索引扫描"),这不是那么有效.

如果您有一个索引(col1,col2,col3),那么当WHERE子句包含对(1)所有3列(2)col1和col1的引用时,您可以预期任何RDBMS将使用索引(以直接方式) col2(3)只有col1.

否则(例如,WHERE子句中只有col3),RDBMS根本不会使用该索引(例如SQLite),或者将执行完整的索引扫描(例如Oracle)[如果没有其他索引更好].

在您的特定示例中,假设id是客户的唯一标识符,将其显示在索引中是没有意义的(除了您的DBMS应为主键或列标记为UNIQUE设置的索引之外).

Answer 3

“索引将按第一个关键元素排序，然后按第二个关键元素排序，依此类推” https://www.qwertee.io/blog/postgresql-b-tree-index-explained-part-1/

Answer 4

一些实现只是按照列的顺序使用分隔符连接值。

另一种解决方案是在 b 树中简单地有一个 b 树。当您点击第一列上的叶子时，您将获得匹配记录的列表和下一列的迷你 b 树，依此类推。因此，索引中指定的列的顺序对该索引是否对特定查询有用有很大的不同。

这是我上周写的一个相关问题：