写在前面

为了更好的学习查询优化和索引,整了一个以空气设备监测的数据生成脚本

Github:https://github.com/uluckyXH/air-device-data-simulation

索引有哪些?


按数据结构分类

  • B+Tree索引 (InnoDB默认)

  • Hash索引(Memonry引擎)

  • Full-Text索引(全文索引)

按物理存储分类

  • 聚簇索引(clustered index)

  • 非聚簇索引(secondary index)

按照字段特性分类

  • 主键索引(PRIMARY KEY)

  • 唯一索引(UNIQUE)

  • 普通索引(INDEX)

  • 复合索引(联合索引)

按照字段个数分类

  • 单列索引

  • 多列索引(复合索引)

按照索引用途分类

  • 覆盖索引

  • 前缀索引

  • 空间索引(SPATIAL)

索引优点

  • 避免全表扫描

  • 减少磁盘I/O次数

  • 通过唯一索引和主键索引

  • 避免数据重复录入

索引缺点

  • 每个索引都需要额外的磁盘空间

  • 索引越多,需要的空间越大

  • INSERT:需要同时插入索引

  • UPDATE:需要更新索引

  • DELETE:需要删除索引

  • 数据更新时,索引需要同步更新

  • 索引过多会影响更新速度

  • 需要定期维护和优化

  • 如果数据量很小,优化器可能不使用索引

  • 某些查询条件下索引可能失效


索引数据结构

首先来看看B+Tree 索引结构

Root Node(根节点)
                        [20]
                      /      \
                     /        \
                    /          \
                   /            \
           [10, 15]              [25, 30]        Internal Node(内部节点)
          /    |    \           /    |    \
         /     |     \         /     |     \
        /      |      \       /      |      \
    [8,9] [11,12,13] [16,17] [21,22] [26,27] [31,32]   Leaf Node(叶子节点)
    
叶子节点实际存储的数据示意:
[8] -> (张三, 8岁, ...)
[9] -> (李四, 9岁, ...)
[11] -> (王五, 11岁, ...)
...以此类推

来看看查询过程演示

1. 从根节点开始:
   [20]
   26 > 20,所以走右边

2. 到内部节点:
   [25, 30]
   25 < 26 < 30,所以走中间

3. 到叶子节点:
   [26,27]
   找到 26

叶子节点的双向链表结构

[8,9] <-> [11,12,13] <-> [16,17] <-> [21,22] <-> [26,27] <-> [31,32]

为什么叶子节点是双向链表结构?

假设有这样一个查询:

SELECT * FROM students WHERE age BETWEEN 11 AND 14;:

查询过程:

首先通过B+树找到11
[20]
                   ↙
           [10, 15]
               ↓
           [11,12,13] ← 找到11的位置

这时候就体现出双向链表的价值了:

[8,9] ←→ [11,12,13] ←→ [16,17]
         ↑
         从这里开始,顺序读取12,13,14

主要用于范围查询:

  • 不需要回到树上重新搜索

  • 可以直接在链表上遍历

  • 支持范围的前后遍历

什么是双向链表?
前一个节点的指针 ↔ 数据 ↔ 下一个节点的指针

        上一节车厢  ←→    当前车厢   ←→   下一节车厢
       [数据 | 指针] ←→ [数据 | 指针] ←→ [数据 | 指针]
示例
比如存储 1,2,3 三个数字:

[null ← 1 → ] ←→ [ ← 2 → ] ←→ [ ← 3 → null]
  头节点          中间节点        尾节点

每个节点包含:
1. 数据值
2. 指向前一个节点的指针(prev)
3. 指向后一个节点的指针(next)
基本操作演示

遍历操作(双向)

向后遍历:1 → 2 → 3
向前遍历:3 → 2 → 1

插入新节点(比如在2和3之间插入4)

之前: 1 ←→ 2 ←→ 3
之后: 1 ←→ 2 ←→ 4 ←→ 3

删除节点(比如删除2)

之前: 1 ←→ 2 ←→ 3
之后: 1 ←→ 3

双向链表的优点

  1. 可以双向遍历

  2. 删除和插入操作效率高

  3. 可以从任意位置向前或向后遍历

双向链表的缺点:

  1. 占用额外的内存空间(需要存储两个指针)

  2. 插入和删除时需要维护两个指针

在索引中使用双向链表的原因
  1. 方便范围查询

  2. 支持正序和倒序遍历

  3. 提高遍历效率


实际案例(TODO)

TODO...