索引

1. 为什么要有索引

假设这个世界没有索引，那么当我们需要查询数据表时，尤其是面对 GROUP BY、ORDER BY 等查询条件时，需要对整个表进行遍历，显然这个时间复杂度是 O(n)。

虽然对于一些有序的数据，可以使用类似「二分查找」的算法提高查询效率。但是实际数据库中可能会存储上百万条数据，二分查找的性能也会急剧下降。

数据的存储是为了后续的查询需求服务的，为了解决查询时的性能问题，数据库引入了「索引（Index）」的概念。

索引的定义

索引是数据库中的一种数据结构，用于提高查询效率。

对数据表中的某些列创建索引后，数据库会在索引中存储「索引列的值」与「该值在原始数据表中的位置」，方便后续的查询操作。

同原始数据表一样，索引中存储的内容也会存储在磁盘上，根据索引列的类型与数量，可能会占据原始数据表 10% 以上的空间。

2. 索引的使用与更新

2.1. 索引的使用

在数据库接收一个查询请求时，会根据查询条件是否包含了索引的列，判断是否需要使用索引。

在使用索引的情况下：

数据库会根据索引的结构，找到索引中保存的原始记录的位置
（可选）根据原始记录的位置，在数据表中找到对应的记录

很重要的一点，如果查询的列全部包含在索引中，那么数据库会直接使用索引中存储的数据，不会再去查询原始的数据表。

2.2. 索引的更新

如果修改了原始数据表中的内容，比如 INSERT、UPDATE、DELETE 等操作，那么索引中存储的内容也需要同步更新。

3. 索引的数据结构

3.1. B+ 树

本段简单介绍了一下 B+ 树在数据库中的使用，更多细节可以参考 B+ 树章节。

最长用的索引结构是 B+ 树，可以很高效地应对 =, >， GROUP BY， ORDER BY 等查询请求。

B+ 树是一种平衡树，它具有以下特点：

每个节点最多有 M 个子节点，维护了指向其子节点的指针
非叶子节点维护了每一个子节点保存的数据范围，也就是「键值」的范围
所有的数据存储在叶子节点上，叶子节点之间通过双向指针连接
为了保证 B+ 树的查询效率，每个节点维护的子节点数量在 [M/2, M] 之间

一个简单的 B+ 树的示例：

// B+树的基本结构
class BPlusTree {
    // 成员变量
    int M;          // 每个节点最多M个子节点
    Node root;      // 根节点

    // 节点抽象类
    abstract class Node {
        List<Key> keys;     // 键值列表
        boolean isLeaf;     // 是否为叶子节点
    }

    // 内部节点
    class InternalNode extends Node {
        List<Node> children;  // 子节点指针列表
    }

    // 叶子节点
    class LeafNode extends Node {
        List<Value> values;   // 值列表
        LeafNode next;        // 指向下一个叶子节点
        LeafNode prev;        // 指向上一个叶子节点
    }

    // 基本操作
    Value search(Key key);                // 查找操作
    void insert(Key key, Value value);    // 插入操作
    List<Value> rangeSearch(Key start, Key end);  // 范围查询
}

当面对一个查询请求时：

从根节点开始向下遍历
根据每个节点的「键值」范围，确定查询请求需要遍历的子节点
重复步骤 2，找到存储了该键值的叶子节点
遍历叶子节点维护的数据，找到对应的记录

因为 B+ 树的每个节点最多有 M 个子节点，所以每次查询只需要遍历 log_M(N) 个节点，时间复杂度为 O(log_M(N))。

B+ 树的更新相对复杂一些，因为可能涉及到 B+ 树的重新平衡。如果 INSERT 或 DELETE 操作导致某个节点的子节点数量超出了 [M/2, M] 的范围，那么需要进行分裂或合并操作。

INSERT 操作导致当前节点的子节点数量大于 M 时，需要进行节点分裂操作：
1. 从叶子节点的中键开始，将叶子节点分裂为两个节点
2. 将中键插入到父节点中，更新父节点的「键值」范围
3. 如果分裂操作导致父节点也超出了 M 个节点，那么需要递归地进行分裂操作，直到父节点无需分裂或者到达根节点
DELETE 操作导致当前节点的子节点数量小于 M/2 时，需要进行节点合并操作：
1. 将两个相邻的叶子节点合并为一个节点
2. 更新父节点中的键值与指针
3. 如果合并操作导致父节点也小于了 M/2 个节点，那么需要递归地进行合并操作
4. 如果根结点的子节点数量减少为 1，则将根节点唯一的子节点提升为新的根节点，树的高度减少 1

3.2. 哈希索引

另外一个常用于查询的结构是哈希桶，同样也可以作为索引的数据结构。

对于建立了哈希索引的列，每次插入时，数据库都会计算哈希值，保存到哈希索引中。

查询时同样，计算目标的哈希值，直接在哈希桶中找到对应的记录。

哈希索引的优点是查询效率高，但是缺点也很明显，它不支持范围查询，也不支持排序。

3.3. 其他索引

其他索引结构还有：

位图索引：对于性别、状态等字段，可以通过位图来保存，位图索引就针对于这类低基数字段适用的索引
倒排索引：倒排索引会保存单词与单词出现的文档列表，通过单词找到对应的文档列表。也就是通过单词找到对应的记录，因此常用于全文搜索等场景

4. 索引的种类

索引的种类

根据不同的查询需求，索引也分为不同的种类：

主键索引
普通索引
唯一索引
联合索引

5. 索引的优化

如前文所说，索引会占用额外的磁盘空间。同时，在更新数据时，需要同步更新索引，因此过多的索引会导致数据库写入性能降低。

如何恰当的建立索引，是日常工作中经常遇到的挑战。这里列出一些通用的优化建议：

只为必要的字段创建索引。一些字段不会出现在查询条件中，或者查询条件中很少使用，那么就不需要创建索引。
不要创建冗余的索引。如果已经存在了 (a, b) 的联合索引，那么就不需要再创建 a 的索引。
使用联合索引。如果经常需要对多个字段进行查询，那么可以对常用的字段建立联合索引。更进一步，必要时可以考虑覆盖索引，避免查询原始数据表。
使用恰当的索引类型。根据查询需求选择合适的索引类型，比如哈希索引、B+ 树索引等。

6. 索引无效的场景

即使恰当的建立了索引，如果使用不当，依然会无法利用索引，导致查询效率降低。

几个常见的索引无效的场景：

索引列上使用函数。如果索引列上使用了函数，那么索引会失效，比如 SELECT * FROM table WHERE id + 1 = 5。
使用不等式查询。如果查询条件中使用了不等式查询，比如 SELECT * FROM table WHERE id > 5，那么索引会失效。
查询列左侧存在通配符。如果查询条件的左侧存在通配符，那么索引会失效，比如 SELECT * FROM table WHERE name LIKE '%张%'。
使用 OR 查询了非索引列。如果查询条件中使用了 OR 查询，并且存在非索引列，那么索引会失效，比如 SELECT * FROM table WHERE id = 1 OR age = 18。
未按照索引顺序查询。如果查询条件中未按照索引顺序查询，依然无法使用索引，比如存在联合索引 (a, b)，但是查询条件为 SELECT * FROM table WHERE b = 1 AND a = 2。

1. 为什么要有索引​

2. 索引的使用与更新​

2.1. 索引的使用​

2.2. 索引的更新​

3. 索引的数据结构​

3.1. B+ 树​

3.2. 哈希索引​

3.3. 其他索引​

4. 索引的种类​

5. 索引的优化​

6. 索引无效的场景​