CMU 15-445 笔记：08 树索引-Ⅱ

CMU 15-445 笔记：08 树索引-Ⅱ

一、其他索引用法

隐式索引（Implicit Indexes）
大多数DBMS（数据库管理系统）会自动创建索引来实施完整性约束，例如主键和唯一约束。这些索引在创建约束时隐式地生成，无需用户显式指定。
部分索引（Partial Indexes）
部分索引是在整个表的子集上创建的索引，通过WHERE语句形成这个子集。这种方法可能会减少索引的大小和维护开销，因为它只针对满足特定条件的记录进行索引。
覆盖索引（Covering Indexes）
当处理查询所需的所有属性都在索引中可用时，DBMS无需检索元组即可完成整个查询。这种索引被称为覆盖索引。它提高了查询效率，因为DBMS可以直接从索引中获取所需数据，而无需访问表中的数据行。
索引包含列（Index Include Columns）
索引包含列是指在索引中嵌入其他列以支持仅索引查询。这种方法允许DBMS在索引中直接包含额外的列，从而避免在查询时回表查找这些列的数据。
函数/表达式索引（Function/Expression Indexes）
函数/表达式索引将函数或表达式的输出存储为键，而不是原始值。这种索引允许DBMS识别哪些查询可以使用该索引，从而优化查询性能。例如，可以对日期字段进行函数索引，以支持基于日期的查询。

二、Radix Tree 基数树

定义与特点
Radix tree是Trie数据结构的变体，它使用key的数字表示来逐个检查前缀，而不是比较整个key。与Trie不同的是，Radix tree在key不同之前合并节点以表示最大的前缀。
Radix tree的高度取决于key的长度，而不是像B+树那样取决于key的数量。这使得Radix tree在处理长整型数据时具有优势。
应用场景
Radix tree适用于长整型数据的映射。对于长整型数据，使用哈希映射可能会面临哈希冲突和哈希表大小设计的问题。而Radix tree能够快速且节省空间地完成这种稀疏的长整型数据查找。
借助Radix tree，可以实现对于长整型数据类型的路由。例如，可以根据一个长ID快速查找到其对应的对象指针。
与Trie的区别
Trie树一般用于字符串到对象的映射，而Radix tree则更适用于长整数到对象的映射。
Radix tree是一种多叉搜索树，树的叶子节点是实际的数据条目。每个节点有一个固定的、2^n指针指向子节点（每个指针称为槽slot，n为划分的基的大小）。

三、Inverted Indexes 倒排索引

定义与功能
倒排索引存储单词到目标属性中包含这些单词的记录的映射。在DBMS中，这些索引有时称为全文搜索索引。
倒排索引允许用户根据关键字进行搜索，而无需遍历整个数据库。它提高了关键字搜索的效率，因为DBMS可以直接从索引中找到包含关键字的记录。
查询类型
短语搜索：查找按给定顺序包含单词列表的记录。
邻近搜索：查找两个单词在彼此的单词内出现的记录。
通配符搜索：查找包含匹配某种模式（例如正则表达式、LIKE）的单词的记录。
设计决策
存储什么：索引需要至少存储每个记录中包含的单词（由标点符号分隔）。它还可以包括其他信息，如词频、位置和其他元数据。
何时更新：每次修改表时更新倒排索引既昂贵又慢。因此，大多数DBMS会维护辅助数据结构以“暂存”更新，然后批量更新索引。这种方法减少了索引更新的频率和开销。

综上所述，CMU 15-445课程中的树索引-Ⅱ部分涵盖了多种索引用法、Radix Tree基数树以及倒排索引等关键内容。这些索引技术在实际应用中具有广泛的应用价值，能够提高数据库查询的效率和性能。

热门标签