【CMU 15-445】08 树索引-II

Slides
Notes

1. 其他索引用法

• 隐式索引（Implicit Indexes）：大多数DBMS会自动创建索引来实施完整性约束(例如，主键、唯一约束)。

• 部分索引（Partial Indexes）：在整个表的子集上创建索引，（where语句形成子集）。这可能会减少大小和维护开销。

• 覆盖索引（Covering Indexes）：处理查询所需的所有属性都在索引中可用，则DBMS不需要检索元组。DBMS只需根据索引中可用的数据即可完成整个查询。（即，索引的数据中就能满足本次查找，不需要再去检索元组了，无需回表操作）

• 索引包含列（Index Include Columns）：在索引中嵌入其他列以支持仅索引查询。

• 函数/表达式索引（Function/Expression Indexes）：将函数或表达式的输出存储为键，而不是原始值。DBMS的工作是识别哪些查询可以使用该索引。

2. Radix Tree 基数树

一个 radix tree 是 Trie数据结构的变体。它使用 key 的 digital 表示来逐个检查前缀，而不是比较整个 key 。它与trie的不同之处在于，key 中的每个元素都没有一个节点，在key不同之前，节点被合并以表示最大的前缀。

Radix tree 的高度取决于 key 的长度，而不是像B+树那样取决于 key 的数量。指向叶节点的路径表示叶的关键字。并非所有属性类型都可以分解为基数树的二进制可比数字。

对于长整型数据的映射，如何解决Hash冲突和Hash表大小的设计是一个很头疼的问题。

radix树就是针对这种稀疏的长整型数据查找，能快速且节省空间地完成映射。借助于Radix树，我们可以实现对于长整型数据类型的路由。利用radix树可以根据一个长整型（比如一个长ID）快速查找到其对应的对象指针。这比用hash映射来的简单，也更节省空间，使用hash映射hash函数难以设计，不恰当的hash函数可能增大冲突，或浪费空间。

Radix tree是一种多叉搜索树，树的叶子结点是实际的数据条目。每个结点有一个固定的、2^n指针指向子结点（每个指针称为槽slot，n为划分的基的大小）

Trie树一般用于字符串到对象的映射，Radix树一般用于长整数到对象的映射。

3. Inverted Indexes 倒排索引

倒排索引存储单词到目标属性中包含这些单词的记录的映射。在DBMS中，这些索引有时称为全文搜索索引。

大多数主要的DBMS本身都支持倒排索引，但也有专门的DBMS，其中这是唯一可用的表索引数据结构。

（君如理解：倒排索引，它可以进行关键字搜索，因为hash索引和B+树索引对这个的性能都不太好。关键字搜索，主要是怕key的容量非常大。因此可以通过将关键词单词映射到包含单词的一些记录中。）

查询类型：

• 短语搜索：查找按给定顺序包含单词列表的记录。

• 邻近搜索：查找两个单词在彼此的单词内出现的记录。

• 通配符搜索：查找包含匹配某种模式(例如，正则表达式，like)的单词的记录。
  设计决策：

• 存储什么：索引需要至少存储每个记录中包含的单词(由标点符号分隔)。它还可以包括其他信息，例如词频、位置和其他元数据。

• 何时更新每次修改表时更新倒排索引既昂贵又慢。因此，大多数DBMS将维护辅助数据结构以“暂存”更新，然后批量更新索引。