是什么在超过1列B-tree索引是什么样子？(what does a B-tree index on

所以，我读了有关索引和实施，我偶然发现了这个网站，有B树索引的简要说明：

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

B树索引非常有意义对于那些只在单个列，但让我们说我创建具有多个列的索引的索引，怎么那么B树工作？什么是在B树中的每个节点的值？

举例来说，如果我有这样的表：

table customer:
id    number
name   varchar
phone_number   varchar
city   varchar

我创建一个索引上：（ID，姓名，市）

然后运行下面的查询：

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

这如何查询使用多列索引，或者它不使用它，除非指数为（市，编号，名称）或（市，姓名，身份证），而不是创造出来的？

Answer 1:

试想一下，关键是通过一个Python元组（COL1，COL2，COL3）...索引操作涉及比较代表tuple_a与tuple_b ......如果你不知道col1和col2上，你有兴趣的哪个值，但只有COL3，那么它会读取整个指数（“全索引扫描”），这是效率不高。

如果您对（COL1，COL2，COL3）的索引，那么你可以期望，任何RDBMS将使用指数（以直接的方式），当WHERE子句包含引用（1）所有3列（2）既col1和COL2（3）仅COL1。

否则（例如，仅在WHERE子句中COL3），无论是RDBMS不会使用该索引的所有（如SQLite的），还是会做一个完整的索引扫描（如Oracle）如果没有其他指标更好。

在具体示例中，假设该id是客户的唯一标识符，它是没有意义的以使其显示在索引（比你的DBMS应设置为一个主键或列的索引的其他记为唯一的）。

Answer 2:

对于大多数实施方案中，关键是简单地较长的键，包括所有的键值，具有隔板。没有魔法有;-)

在您的例子可以在键值看起来像

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

一个的这些指标与复合键的特征是，中间树节点可以在一些情况下被用于“覆盖”的查询。

例如，如果查询是要找到名称和城市给出的ID，因为ID是第一个在指数，该指数可以通过这个有效地搜索。一旦中间节点，它可以“解析”的名称和城市，从钥匙，并不需要去叶节点读取相同。

但是，如果想查询也显示电话号码，然后当完全记录被发现的逻辑将随之回落叶子。

Answer 3:

有些实现只是在连接值的列的顺序，用分隔符。

另一种解决方案是简单地拥有B树中的B树。当你点击第一列叶子，你就获得了匹配的记录列表和下一列的小型B树，等等。因此，在索引指定的列的顺序而基于该指数是否会针对特定的查询有用的巨大差异。

这里有一个相关的问题我上周写道：

请问SQL服务器跳叶使用复合聚集索引的时候？

Answer 4:

在Oracle组合键可以使用索引即使前导列进行过滤。这是通过三种机制来完成：

快速全索引扫描，其中多嵌段读取用于遍历整个索引段。
索引全扫描，其中指数在块的逻辑顺序读取（我相信我读到，在最新版本的Oracle可以使用这个多块读取，但真的是你应该依靠单块读取）
一个inddex跳跃扫描，其中非常低的基数为非断言前导列允许Oracle执行多个索引范围扫描，一个用于前导列（多个）的每一个唯一值。这些都是在我的经验非常罕见的。

寻找理查德·富特或乔纳森·刘易斯在Oracle的索引内部更多信息的文章。

Answer 5:

除了“复合键”机制已经描述过的，一种可能性是kdtree它就像一个二叉树，但是当你遍历每个级别通过你循环k尺寸。即，树的第一级上的第一维分离成两个部分，第二级分裂第二维度时， k+1个电平再次分裂第一维等。这允许在任何数量的数据的有效的分区的尺寸。这种方法是在“空间”数据库（如Oracle空间，PostGIS的，等等）常见，但可能不会在“常规”多索引的表一样有用。

http://en.wikipedia.org/wiki/Kd-tree

Answer 6:

It can use the (id,name,city) index to satisfy a "City = ? " predicate, but very very inefficently.

In order to use the index to satisfy this query it would need to walk most of tree structure looking for entries with the desired city. This is still probably an order of magnatude faster than scanning the table!

An index of (city,name,id) would be the best index for your query. It would find all the desired city entries easily and would not need to access the underlying table to get the id and name values.

文章来源: what does a B-tree index on more than 1 column look like?