CMU::15-445/645::Tree Indexes 笔记

2021 Sep 22

树形索引第一部分

表索引

在数据库系统中，有许多不同的数据结构，可以用于内部元数据、核心数据存储、临时数据结构或表索引等目的。对于表索引，可能涉及到带有范围扫描的查询。

表索引是一个表的列的子集的副本，它被组织和(或)排序，以使用这些属性的子集进行有效的访问。因此，DBMS 可以查询表索引的辅助数据结构，而不是进行顺序扫描，以更快地找到 Tuple 。DBMS 确保表和索引的内容在逻辑上总是同步的。

在每个数据库要创建的索引数量之间存在着一个权衡。尽管更多的索引使得查询速度更快，但索引也会使用存储空间并需要维护。DBMS 的工作是找出用于执行查询的最佳索引。

B+树

B+Tree 是一种自平衡的树形数据结构，它可以保持数据的分类，并允许在 O(log(n))中进行搜索、顺序访问、插入和删除。它为面向磁盘的 DBMS 的读/写大型数据块而优化。

几乎所有支持保序索引的现代 DBMS 都使用 B+Tree。有一种特定的数据结构叫做 B-Tree，但是人们也用这个词来泛指一类数据结构。原始的 B-Tree 和 B+Tree 之间的主要区别是，B-Tree 在所有节点中存储键和值，而 B+Tree 只在叶节点中存储值。现代 B+Tree 的实现结合了其他 B-Tree 变体的特征，例如 B\(^{link}\)-Tree 中使用的兄弟姐妹指针。

从形式上看，B+树是一棵具有以下特性的 M-way 搜索树。

它是完全平衡的（即，每个叶子节点都在相同的深度）。
除根以外的每个内部节点至少有一半是满的（M/2 - 1 <= 键的数量 <= M - 1）。
每个有 k 个键的内部节点都有 k+1 个非空子节点。

B+Tree 中的每个节点都包含一个键/值对数组。这些对中的键是由索引所基于的属性派生的。这些值将根据一个节点是内部节点还是叶子节点而有所不同。对于内部节点，值数组将包含指向其他节点的指针。叶子节点值的两种方法是记录 ID 和 Tuple 数据。记录 ID 指的是一个指向 Tuple 位置的指针。有 Tuple 数据的叶子节点在每个节点中存储 Tuple 的实际内容。

每个节点的数组都（几乎）是按键排序的。

实践中节点中键和值是分开存储的

插入

要在 B+树中插入一个新的条目，必须沿着树向下遍历，并使用内部节点来确定将值插入哪个叶子节点。

找到正确的叶子 L。
按排序顺序将新条目添加到 L 中。
- 如果 L 有足够的空间，操作就完成了。
- 否则将 L 分成两个结点 L 和 L2。均匀地重新分配条目，并将中间的键复制上去。将指向 L2 的索引条目插入 L 的父节点中。
要分割一个内部节点，均匀地重新分配条目，但要把中间的键向上推。

可视化演示网址

删除

在插入过程中，当树变得太满时，我们偶尔不得不分割叶子，而如果删除导致树少于半满，我们必须进行合并，以重新平衡树。

找到正确的叶子 L。
删除条目。
- 如果 L 至少有一半是满的，那么操作就完成了。
- 否则，你可以尝试重新分配，从兄弟姐妹那里借用。
- 如果重新分配失败，则合并 L 和同胞。
如果合并发生了，你必须删除父类中指向 L 的条目。

可视化演示网址

条件选择

因为 B+Tree 是按排序的，查找时遍历速度很快，也不需要整个键。如果查询提供了搜索键的任何属性，DBMS 可以使用 B+Tree 索引。这与散列索引不同，散列索引需要搜索键中的所有属性。

非唯一索引

像散列表一样，B+Trees 可以通过重复键或存储值列表来处理非唯一的索引。在重复键的方法中，使用相同的叶子节点布局，但重复的键被多次存储。在值列表的方法中，每个键只存储一次，并保持一个唯一值的链接列表。

重复键

在 B+Tree 中，有两种方法来重复键。

第一种方法是将记录 ID 作为键的一部分来附加。由于每个 Tuple 的记录 ID 是唯一的，这将确保所有的键都是可识别的。DBMS 可以根据部分键来查找 Tuple 。

第二种方法是允许叶子节点溢出到包含重复键的溢出节点。虽然没有多余的信息被存储，但这种方法的维护和修改更加复杂。

聚簇索引

表按照主键指定的排序顺序存储，作为堆组织的或索引组织的存储。由于一些 DBMS 总是使用聚簇索引，如果一个表没有明确的主键，它们会自动地将隐藏的行 ID 作为主键，但是其他的 DBMS 根本就不能使用它们。

堆聚簇

Tuple 在堆的页面中使用聚簇索引指定的顺序进行排序。如果聚类索引的属性被用来访问 Tuple ，DBMS 可以直接跳到这些页面。

索引扫描页排序

由于直接从非聚簇索引中检索 Tuple 的效率很低，DBMS 可以首先找出它所需要的所有 Tuple ，然后根据它们的页面 id 进行排序。

树形索引第二部分

LC0Gnkk

B+树设计选择

节点尺寸

根据存储介质的不同，我们可能喜欢更大或更小的节点尺寸。例如，存储在硬盘上的节点通常是以兆字节为单位，以减少寻找数据所需的次数，并将昂贵的磁盘读取分摊到一大块数据上，而内存数据库可能使用小到 512 字节的页面大小，以便将整个页面放入 CPU 缓存，并减少数据的碎片。这种选择也取决于工作负载的类型，如点查询会喜欢尽可能小的页面，以减少不必要的额外信息的加载量，而大的顺序扫描可能更喜欢大的页面，以减少它需要做的检索的数量。

合并阈值

虽然 B+Trees 有一条规则，即在删除后合并溢出的节点，但有时暂时违反该规则以减少删除操作的次数可能是有益的。例如，急于合并可能会导致激动，大量连续的删除和插入操作会导致不断的分裂和合并。它还允许分批合并，即多个合并操作同时发生，减少在树上进行昂贵的写锁存的时间。

不同长度的 keys

目前我们只讨论了具有固定长度键的 B+Trees。然而，我们可能也想支持可变长度的键，比如说一个大键的小子集导致大量空间浪费的情况。对此有几种方法。

指针：我们可以不直接存储键，而只是存储一个指向键的指针。由于必须为每个键追寻一个指针的低效率，在生产中使用这种方法的唯一地方是嵌入式设备，其微小的寄存器和缓存可能会从这种空间的节省中受益。
可变长度的节点：我们也可以像平常一样存储 key 并允许可变长度的节点。这是不可行的，而且由于处理可变长度的节点有很大的内存管理开销，所以基本上没有使用。
填充：我们可以不改变 key 的大小，而是将每个 key 的大小设置为最大 key 的大小，并将所有较短的 key 填充起来。在大多数情况下，这是一个巨大的内存浪费，所以你也不会看到有人使用这个方法。
key 映射/重定向：几乎每个人都在使用的方法是用一个索引来代替键值对在一个单独的字典中的键值。这可以大大节省空间，并有可能缩短点查询（因为索引指向的键值对与叶子节点指向的键值对完全相同）。由于字典索引值的大小较小，有足够的空间将每个键的前缀放在索引旁边，可能允许一些索引搜索和叶子扫描，甚至不必追寻指针（如果前缀与搜索键有任何不同）。

节点内搜索

一旦我们到达一个节点，我们仍然需要在该节点内进行搜索（要么从内部节点找到下一个节点，要么在叶子节点中找到我们的键值）。虽然这相对简单，但仍有一些权衡需要考虑。

线性：最简单的解决方案是直接扫描节点中的每个键，直到我们找到我们的键。一方面，我们不必担心对键的排序，使插入和删除更快。另一方面，这是相对低效的，每次搜索的复杂度为 O(n)。
二分：一个更有效的搜索方案是保持每个节点的排序，并使用二分搜索来寻找键。这就像跳到一个节点的中间并根据键的比较向左或向右转动一样简单。这种方式的搜索效率更高，因为这种方法每次搜索的复杂度只有 O(ln(n))。然而，插入变得更加昂贵，因为我们必须维护每个节点的排序。
内插法：最后，在某些情况下，我们可以利用插值法来寻找 key。这种方法利用了存储在节点上的任何元数据（如最大元素、最小元素、平均数等），并利用它来生成 key 的大致位置。例如，如果我们在一个节点中寻找 8，我们知道 10 是最大的键，10-（n+1）是最小的键（其中 n 是每个节点中的键的数量），那么我们知道从最大的键向下 2 个槽开始搜索，因为在这种情况下，离最大键一个槽的键必须是 9。尽管这是我们给出的最快的方法，但由于其对具有某些属性（如整数）和复杂性的键的适用性有限，这种方法只在学术数据库中出现。

优化

前缀压缩

大多数情况下，当我们在同一节点中拥有键时，每个键的一些前缀会有部分重叠（因为在排序的 B+Tree 中，类似的键最终会紧挨着彼此）。我们可以简单地在节点的开头存储一次前缀，然后只在每个槽中包括每个键的独特部分，而不是多次将这个前缀作为每个键的一部分来存储。

重复

在一个允许非唯一键的索引的情况下，我们最终可能会出现叶子节点包含相同的的叶子节点，而这些叶子节点上又附有不同的值。这种情况的一个优化方法是只写一次键一次，然后在它后面加上所有相关的值。

后缀截取

在大多数情况下，内部节点的键项只是作为路标，而不是其实际的键值（因为即使一个键存在于索引中，我们仍然要搜索到底部，以确保它没有被删除）。我们还可以利用这一点，在一个给定的内部节点只存储每个键的最小区分前缀。虽然我们可以使其最小化为只有一个不同的字符/数字，但在最后留下一些冗余的数字可能是有益的，以使由于相同的前缀而导致的无法确定的插入不太可能发生。在这种情况下，我们将不得不搜索到树的底部以找到完整的键（或者在该键被删除的情况下，取决于叶子节点的最小或最大键）。

批量插入

当 B+Tree 最初建立时，必须以通常的方式插入每个键，这将导致不断的分割操作。由于我们已经给叶子提供了兄弟姐妹的指针，如果我们构建一个叶子节点的排序链表，然后使用每个叶子节点的第一个键轻松地从下往上建立索引，那么初始插入数据的效率会高很多。请注意，根据我们的情况，我们可能希望尽可能紧密地打包叶子以节省空间，或者在每个叶子中留出空间，以便在有必要进行分割之前进行更多的插入。

指针替换

因为 B+Tree 的每个节点都存储在缓冲池的一个页面中，所以每次我们加载一个新的页面时，都需要从缓冲池中获取它，这需要锁存和查找。为了完全跳过这一步，我们可以用实际的原始指针来代替页面 ID（称为 “swizzling”），完全避免缓冲池的获取。与其手动获取整个树并手动放置指针，我们可以在正常遍历索引时简单地存储从页面查询中得到的指针。请注意，我们必须跟踪哪些指针被刷新，并在它们所指向的页面被取消钉住时，将它们重新刷新为页面 ID。

额外的索引使用

隐式索引：如果你创建了一个主键或唯一约束，大多数 DBMS 会自动创建一个隐式索引来执行完整性约束，但不是参照性约束。
局部索引：在许多情况下，用户可能不需要为表中的每一个元组建立索引，可能只对数据的一个子集感兴趣。部分索引是一个具有某些条件或 “where 子句"的索引，因此它包括表的一个子集。这可能会减少维护表的大小和开销，避免用不必要的数据污染缓冲池缓存。例如，部分索引的一个常见用途是按日期范围（每个月、每年等）划分索引。

CREATE INDEX idx_foo ON foo (a, b) WHERE c = 'WuTang';

SELECT b FROM foo WHERE a = 123 AND c = 'WuTang';

索引覆盖：如果处理查询所需的所有属性在一个索引中都是可用的，那么 DBMS 就不需要检索 Tuple。DBMS 可以仅仅根据索引中的可用数据来完成整个查询。换句话说，覆盖索引只是用来定位表中的数据记录，而不是用来返回数据。这减少了对 DBMS 的缓冲池资源的争夺。

CREATE INDEX idx_foo ON foo (a, b);

SELECT b FROM foo WHERE a = 123;

索引包含列：索引包括的列允许用户在索引中嵌入额外的列，以支持仅有索引的查询。这些额外的列被存储在叶子节点中，实际上不是搜索键的一部分。

CREATE INDEX idx_foo ON foo (a, b) INCLUDE (c);

SELECT b FROM foo WHERE a = 123 AND c = 'WuTang';

函数/表达式索引：索引也可以在函数或表达式上创建。索引不需要以它们在其基础表中出现的相同方式来存储键。相反，函数/表达式索引将函数或表达式的输出作为键来存储，而不是原始值。DBMS 的工作是识别哪些查询可以使用该索引。

SELECT * FROM users WHERE EXTRACT(day_of_week FROM login) = 2;

CREATE INDEX idx_user_login ON users (EXTRACT(dow FROM login));

Trie 索引

请注意，B+Tree 中的内部节点键不能告诉你某个键是否存在于索引中。每次查询一个键时，你必须遍历叶子节点。 Trie 索引允许我们在树的顶端知道一个键是否存在。Trie 索引使用键的数字表示法来逐一检查前缀，而不是比较整个键。 Trie 索引有许多有用的特性。其一，它们的形状只取决于可以空间和长度，不需要重新平衡操作。此外，所有的操作都有 O(k)的复杂性，其中 k 是 key 长度。这是因为通往叶子节点的路径代表了叶子的 key。一个三角形层面的跨度是每个部分 key/数字所代表的比特数。

Radix 树

Radix 树是 Tree 数据结构的一个变种。它与 trie 索引不同的是，只有一个子节点的节点被省略了。相反，节点被合并以代表键不同之前的最大前缀。Radix 树可以产生假阳性，所以 DBMS 必须始终检查原始元组，看一个键是否匹配。径向树的高度取决于键的长度，而不是像 B+ 树那样取决于键的数量。通往叶子节点的路径代表叶子的键。并非所有的属性类型都可以被分解成二进制的可比数字用于 Radix 树。

倒置索引

一个倒置的索引存储了一个词与目标属性中包含这些词的记录的映射。这些有时被称为 DBMS 中的全文搜索索引。倒置索引对关键词搜索特别有用。大多数主要的 DBMS 都支持倒置索引，但也有一些专门的 DBMS，在那里这是唯一可用的表索引数据结构。

查询类型

倒置索引允许用户进行三种无法在 B+Tree 上进行的查询。首先，倒置索引允许短语搜索，它可以找到包含按给定顺序排列的单词列表的记录。它们还允许近似搜索，记录两个词在彼此的 n 个词内出现的地方。第三，倒置索引允许通配符搜索，它可以找到包含与某些模式（如正则表达式）相匹配的词的记录。

设计决策

开发倒置树的两个主要决策是存储什么和何时更新。倒置索引至少需要能够存储每条记录中包含的单词（用标点符号分隔）。它们还可能包括额外的信息，如词频、位置和其他元数据。每次表被修改时，更新一个倒置的索引是昂贵而缓慢的。正因为如此，倒置索引通常会维护辅助数据结构来进行阶段性更新，然后分批更新索引。