如何组织多列B树索引

我想了解更好的索引组织。假设我们有一个表2列：如何组织多列B树索引

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

我们想创建一个索引：

CREATE INDEX IDX_MultiColIdx on user(name,age)

如何将B树索引的组织是什么样子？

如果有一列，如年龄，组织是明确的：每个非叶子节点将包含一组将被用于搜索的整数键。哪些值包含我们的IDX_MultiColIdx B树索引的节点？

来源

2010-09-15 Tim

哪个值包含了我们IDX_MultiColIdx B树索引的节点？

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-15 07:15:10 Quassnoi

插入或搜索键时，您将不得不忽略长度，因为不等式如'... where colm>'xyz'将变得非常低效。 – paxdiablo 2010-09-15 07:19:53

@paxdiablo：“忽略长度”是什么意思？ – Quassnoi 2010-09-15 07:36:08

这是关于你的“而VARCHAR是以其长度作为前缀”的评论。我的意思是，如果您使用“”作为比较键，它将主要以“名称长度”顺序而不是“名称”顺序。换句话说，它将排序'a，b，c，aa，ff，bbbbb'而不是'a，aa，b，bbbbb，c，ff'。存储长度的位置并不重要（只要您可以在密钥中找到它），只是不要使用长度进行排序/比较。 – paxdiablo 2010-09-15 07:44:16

我假设你问的内部数据库实现，因为你提到'非叶节点'。

b树中的内部节点不需要存储完整的密钥;他们只需要存储分隔符。前缀和后缀压缩意味着内部节点可以非常密集，因此可以减小b树的高度，从而提高整体性能。

例如，给定索引与连续键<'非常长的字符串'，314159>和<'不同一个字符串'，9348>，所有内部节点需要表示的是这些键之间的分隔，可以用一个字符表示。以类似的方式，当要在内部节点中分离的键具有共同的前缀时，该前缀只需要被存储一次，并且它们分开的点表示。

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

有关此方面的很好参考，请参阅Gray的“交易处理：概念和技术”& Reuter，如果需要更多详细信息，请参阅参考资料。

来源

2010-09-15 07:47:36 janm

如何组织多列B树索引

回答

相关问题