2

我想了解更好的索引组织。想象一下，我们有一个有 2 列的表：

CREATE TABLE user( 
  name varchar(100)
 ,age int)

我们想创建一个索引：

CREATE INDEX IDX_MultiColIdx on user(name,age)

B-Tree 索引组织会是什么样子？

在一个列的情况下，例如age，组织是明确的：每个非叶节点都将包含一组整数键，用于搜索。哪些值包含我们的IDX_MultiColIdx B-Tree 索引的节点？

4

2 回答 2

4

哪些值包含我们的IDX_MultiColIdx B-Tree 索引的节点？

的值name和age行指针（RID/ROWID或聚集键，取决于表组织），按字典顺序排序。

它们的存储方式取决于数据类型和数据库系统。

通常，CHAR存储在其大小的右侧填充空格，而VARCHAR在其长度之前添加。

MyISAM并且一些其他引擎可以使用密钥压缩：一组密钥的匹配部分只存储一次，而其他密钥只存储不同的部分，如下所示：

Hamblin
Hamblin, California
Hamblin (surname)
Hambling Baronets
Hambly
Hambly Arena    
Hambly Arena Fire
Hambo
Hambo Lama Itigelov
Hambok
Hambone

将存储为：

Hamblin
[7], California
[7] (surname)
[7]g Baronets
Hambly
[6] Arena   
[6] Arena Fire
Hambo
[5] Lama Itigelov
[5]k
[5]ne

，其中的意思是“从前一个键中[x]获取前导字符”x

于 2010-09-15T07:15:10.147 回答
1

我假设您询问的是内部数据库实现，因为您提到了“非叶节点”。

b-tree 中的内部节点不需要存储完整的密钥；他们只需要存储分隔键。前缀和后缀压缩意味着内部节点可以非常密集，因此降低了 b-tree 的高度，从而提高了整体性能。

例如，给定一个具有顺序键 <'A very long string', 314159> 和 <'Not the same string', 9348> 的索引，所有内部节点需要表示的是这些键之间的分隔，可以是以单个字符表示。以类似的方式，当内部节点中要分离的键具有公共前缀时，该前缀只需要存储一次并表示它们的分歧点。

叶节点需要存储完整的键值，并且可以存储在链表中用于键顺序遍历。叶节点页面可以通过使用前缀压缩或其他技术进行压缩，以进一步降低树的高度。

有关这方面的良好参考，请参阅 Gray & Reuter 的“事务处理：概念和技术”，如果您想了解更多详细信息，请遵循参考。

于 2010-09-15T07:47:36.063 回答