15
磁盘地址
21
89
48
13
1
0x08
p2
64
关键字检索规则
王五
p1
left
data
0
34
10
30
78
磁盘块5
right
xxx
Page(16k）
19
InnoDB 主键索引
0x02
151xxxx2353
B树的数据分裂
3
0x03
151xxxx5323
name
.......
........
66
磁盘块3
李四
0x12301
gender
12
26
.........
8
56
辅助索引（name字段）
...
0x05
50
60
0x06
17
0x56
9
52
Primary Key
0xC7
35
0x12302
磁盘块4
65
23
张三
InnoDB中索引采用的B+ Tree的存储结构
InnoDB引擎的索引实现
磁盘块9
只有叶子节点才存储数据
p3
0x0y
磁盘块8
磁盘块2
在数据库索引中，一个节点表示一个Page页
55
33
磁盘块1
31
索引
0x01
0x0z
MyISAM引擎的索引实现
根据name查询
0x07
磁盘块6
81
87
1000*1000=1000000(路)
0x10
27
90
table: user
磁盘块10
赵六
151xxxx6023
0x0x
where name = \"王五\"
id
5
77
phone
逻辑顺序和物理存储顺序一致
0x77
2
磁盘块7
1000路
4
24
关键字数（N），度：N+x
61
0x12303
索引使用多路平衡树来存储（深度小了，磁盘IO次数更少）
92
69
0x09
0x04
节点拥有的子树数量称为度（Degree）
查找
Max Degree=3但节点key数量不能超过2
99
36
0x6A
20
0xF3
索引使用二叉树结构推演（数据越大树越深，磁盘IO次数越多）
72
161xxxx3413
省略子节点
index:user(id)
假设一条记录是16Bytes，那么一个叶子节点可以存储10条，那么总的记录条数：1000000 * 10 =1千万条记录
钱七
B+树的存储数据量
主键索引 where id=19
0x12304
key < 17 ->0x02key=17 -> 命中<17key<35 -> 命中key=35 ->命中key>35 ->0x04
82
非主键索引的检索方式
节点拥有的子节点数量：关键字树：N度（分路数）： N
王八
