SQL Performance Explained: Anatomy of an Index

Index 索引是数据库中一个独特的结构，通过使用 create index 语句来构建。这意味着一个索引是冗余的，创建索引不会改变表数据。它会创建一个新的数据结构，并指向该表。总而言之，索引有自己的空间，且高度冗余 redundant，并指向存储在不同位置的实际信息。

Clustered Indexes

SQL Server 和 Mysql (InnoDB) 对索引是什么有更加广泛的视角。它们将完全由索引结构构成的表，称为聚集索引 clustered indexes。这些表在 Oracle 叫 Index Organized Tables (IOT)。

搜索数据库索引就像查找电话目录一样，核心思想是所有实例都是按顺序排列的。查找有序的数据快速且简单，因为顺序决定了条目位置。

数据库索引比电话目录更加复杂一些，因为它会不断变化。每次变化都去修改目录是不可行的，因为实体之间没有额外空间。目录修改一般会等到累计到足够的变化后再处理，而数据库等不了那么久，它必须处理 insert 插入，delete 删除和 update 更新。

数据库结合了两种数据结构来应对挑战：双向链表 double linked list 和搜索树 search tree，这两种结构解释了数据库的大部分性能特征。

The Index Leaf Nodes

索引的首要目标是提供索引数据的排序表示。然而，由于插入语句 insert statement 需要为新的数据移动后续条目。移动大量数据是十分耗时的，这样会导致 insert 插入语句很慢。解决方案是建立一个独立于内存物理顺序的逻辑顺序。

逻辑顺序通过双向链表建立，每个头都有指向两侧邻居的指针。新 node 插入的时候，修改两侧的指针指向。 node 的物理地址不重要，因为双向链表维护的是逻辑顺序。

数据库使用双向链表来连接所谓是索引叶节点 leaf nodes。每个叶节点存储在一个数据库块 database block 或叶 page 中，即数据库的最小存储单元。每块都是一样的大小，通常几千字节 kilobytes。数据库会尽可能利用每个块的空间，并在每个块中存储尽可能多的索引条目。这意味着索引顺序在两个层面维护：每个叶节点内的索引条目，以及叶节点之间通过双向链表连接。

The Search Tree (B-Tree)

索引的叶子节点以任意顺序存储，磁盘上的位置并不对应索引顺序的逻辑位置。数据库需要一个辅助结构，一遍在打乱的叶面中快速定位条目，这就是平衡搜索树 balanced search tree，简称为 B 树。

                          [ Root Node ]
                          [ 57 ] [ 90 ]
                         /             \
                        /               \
        [ Branch Node ]                  [ Branch Node ]
      [ 46 ] [ 53 ] [ 57 ]             [ 83 ] [ 85 ] [ 90 ]
        /      |       \                 /      |       \
       /       |        \               /       |        \
      ↓        ↓         ↓             ↓        ↓         ↓
   [Leaf]   [Leaf]    [Leaf]        [Leaf]   [Leaf]    [Leaf]
   [ 40 ]   [ 46 ]    [ 55 ]        [ 67 ]   [ 83 ]    [ 85 ]
   [ 43 ]   [ 53 ]    [ 57 ]        [ 83 ]   [ 85 ]    [ 90 ]
   [ 46 ]   [ 53 ]    [ 57 ]        [ 83 ]   [ 85 ]    [ 90 ]
     ↕        ↕         ↕             ↕        ↕         ↕
   [Leaf] ⇔ [Leaf] ⇔  [Leaf]   ⇔    [Leaf] ⇔ [Leaf] ⇔  [Leaf]

双向链表在 leaf node 叶节点之间建立了逻辑顺序，根节点 root node 和分支节点 branch node 在叶节点之间进行快速搜索。这里每个分支节点对应下面所有叶节点的最大值，根据此方案，分支会持续构建，直到所有叶节点都被分支节点覆盖。

下一层通过类似的方式去构建，该过程不断重复，知道最终所有 key 都适配到单个节点中，即根节点 root node。该结构是一个平衡搜索树 balanced search tree 因为树的深度在每个位置都相同，根节点到每个叶节点的深度都是相同的。

树遍历 tree traversal 是一种非常高效的操作，被称为索引第一效能 the first power of indexing。这主要是因为树的平衡性，它允许以相同的步数访问所有元素，其次是因为树的深度层对数增长。这意味着树深度的增长速度，对比叶节点增加的速度，十分的缓慢。真实世界的有百万条记录的索引只有 4 或 5 层的深度，6 层的深度就很罕见了。

Slow Indexes, Part 1

尽管树遍历 tree traversal 效率极高，但在某些情况下，索引查找的速度仍不如预期。这种矛盾长期以来助长了 “索引退化” degenerated index 这一迷思。该迷思宣称重建索引 index rebuild 是解决性能问题的灵丹妙药。然而，即使使用了索引，一些语句依然执行很慢。

慢索引查找的第一个要素 ingredient 是叶节点链。例如要查找 57，根据上面示例可以看到，有两个 57。数据库必须要读取下一个叶节点，来判断是否有更多的匹配值。这意味着，索引查找不仅要按执行树遍历，还需要跟随叶子节点链。

另一个慢索引查找的要素是回表 table access。即使是一个叶子节点，也可能包含许多匹配项，通常多达数百个。对应表数据通常分散在许多表块中，这意味着每次命中都需要额外的表访问。

一次索引查找要求三步：

树遍历 tree traversal
遍历叶子阶段链
获取数据

树遍历是唯一一个对访问块数量有上线的步骤，即索引深度。其他两步可能要访问很多块，他们会导致慢索引查询。

Logarithmic Scalability 对数可扩展性

在搜索树中，对数的基对应每个分支节点的条目数量，而指数对应树的深度。如果每个节点有 4 个分支，则树的深度是 $log_{4}(number-of-index-entries)$ 即实体数量以 4 为底的对数。该对数增长允许索引示例搜索上百万个记录，但树的深度只有 10，而真实世界的索引会更加高效。因此，影响树深度以及查找性能的主要因素，是每个树节点中的条目数量。这个数字在数学上对应对数的底数，底数越高，树的深度越浅，遍历速度越快。

数据库将这一概念发挥到极值，在每个节点中尽可能多地存放条目，通常达数百个。这意味着，每增加一个新的索引层级，就能支持比之前多一百倍的条目。

原始的 “慢索引” 迷思的错误思维是人为索引查询只会遍历树，因此会错误认为慢索引是由于树被破坏或不平衡导致的。事实上，可以直接询问大多数数据库它们是如何使用索引的。在这方面，Oracle 数据库表现得相当详尽，它提供了三种不同的操作来描述基本的索引查找过程：

Index Unique Scan
索引唯一扫描仅执行树遍历操作。 Oracle 数据库在确保唯一性约束的条件下，会采用此操作，以确保搜索条件最多匹配一个条目。
Index Pages Scan
索引范围扫描执行树遍历，并沿着叶子节点查询所有匹配条目。这是备用操作，如果有多个条目可能符合搜索条件。
Table Access by Index RowID
通过索引行 ID 访问表的操作从表中检索行。此操作针对从前一个索引扫描操作中匹配到的每条记录执行。

关键在于，索引范围扫描可能会读取索引的很大一部分。如果每行数据都要额外访问一次表，那么即使使用了索引，查询也可能变得缓慢。

The Index Leaf Nodes#

The Search Tree (B-Tree)#

Slow Indexes, Part 1#

The Index Leaf Nodes

The Search Tree (B-Tree)

Slow Indexes, Part 1