简析数据库索引中范围匹配的问题
索引的数据
| 编号 | 字段a | 字段b |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 1 | 2 |
| 3 | 1 | 3 |
| 4 | 1 | 4 |
| 5 | 1 | 5 |
| 6 | 1 | 6 |
| 7 | 1 | 7 |
| 8 | 1 | 8 |
| 9 | 2 | 1 |
| 10 | 2 | 2 |
| 11 | 2 | 3 |
| 12 | 2 | 4 |
| 13 | 2 | 5 |
| 14 | 2 | 6 |
| 15 | 2 | 7 |
| 16 | 2 | 8 |
| 17 | 3 | 1 |
| 18 | 3 | 2 |
| 19 | 3 | 3 |
| 20 | 3 | 4 |
| 21 | 3 | 5 |
| 22 | 3 | 6 |
| 23 | 3 | 7 |
| 24 | 3 | 8 |
索引使用分析
- a=1,b>5 走索引则能把编号6-8确定
- a<=2,b>5 走索引只能把编号1-16确定，因为要对比b时，值已经不是按顺序排序
因为实际存储不是线性存储，还需要树状结构的查询，因此必须能比较大小才能走索引，即字段不能出现不按照顺序排序。
B+树存储
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
┌─────────────────┐
│ (1,1,page1addr) │
│ (1,7,page2addr) │
│ (2,5,page3addr) │
│ (3,3,page4addr) │
│ │
│ page0 │
└─────────────────┘
┌───────┐ ┌───────┐ ┌───────┐ ┌───────┐
│ (1,1) │ │ (1,7) │ │ (2,5) │ │ (3,3) │
│ (1,2) │ │ (1,8) │ │ (2,6) │ │ (3,4) │
│ (1,3) │ │ (2,1) │ │ (2,7) │ │ (3,5) │
│ (1,4) │ │ (2,2) │ │ (2,8) │ │ (3,6) │
│ (1,5) │ │ (2,3) │ │ (3,1) │ │ (3,7) │
│ (1,6) │ │ (2,4) │ │ (3,2) │ │ (3,8) │
│ │ │ │ │ │ │ │
│ page1 │ │ page2 │ │ page3 │ │ page4 │
└───────┘ └───────┘ └───────┘ └───────┘
假设一个page能存6条记录，page1addr为page1的地址偏移量
实际读取
- a=1,b>5 通过非叶子节点page0的记录比较，需要读取page1、page2
- a=1,b>=8 需要读取page2
- a<=2,b>5 需要读取page1、page2、page3