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

Question

所以我在阅读索引及其实现时，偶然发现了这个对 b-tree 索引有简要解释的网站:

http://20bits.com/articles/interview-questions-database-indexes/

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 在索引中排在第一位，因此索引可以高效地搜索。一旦进入中间节点，它就可以从键“解析”Name和City，而不需要去叶节点读取相同的内容。

但是，如果查询还想显示电话号码，那么当找到完整记录时，逻辑将沿着叶子向下。