SQLite源码分析8 索引#
数据和索引到底是怎么存在磁盘的？#
一般默认会创建表b树，直接存数据。
b树本身肯定不能存所有数据，因为数据可能巨大。
b树只作为一个架子，存所有数据的key，每个节点只有一页数据，其他大量的实际数据的页号另存成链表，放在overflow页。b树节点的子节点关系都是存在磁盘的，也就是b树的结构都是存好在文件里的。
实际数据只有一个副本。架子里的节点指向对应的数据副本。
其他index树的节点可以说都是指向这些唯一的数据副本。index树必须基于实际数据来创建。当数据发生改变时必须更新相关的index树。
观察create index的流程。
sqlite> explain create index i1 on t2(data);
addr opcode p1 p2 p3 p4 p5 comment
---- ------------- ---- ---- ---- ------------- -- -------------
0 Init 0 33 0 00 Start at 33
1 Noop 0 32 0 00
2 CreateBtree 0 1 2 00 r[1]=root iDb=0 flags=2
3 OpenWrite 0 1 0 5 00 root=1 iDb=0; sqlite_master
4 String8 0 3 0 index 00 r[3]='index'
5 String8 0 4 0 i1 00 r[4]='i1'
6 String8 0 5 0 t2 00 r[5]='t2'
7 SCopy 1 6 0 00 r[6]=r[1]
8 String8 0 7 0 CREATE INDEX i1 on t2(data) 00 r[7]='CREATE INDEX i1 on t2(data)'
9 NewRowid 0 2 0 00 r[2]=rowid
10 MakeRecord 3 5 8 BBBDB 00 r[8]=mkrec(r[3..7])
11 Insert 0 8 2 18 intkey=r[2] data=r[8]
12 SorterOpen 3 0 1 k(2,,) 00
13 OpenRead 1 6 0 2 00 root=6 iDb=0; t2
14 Rewind 1 20 0 00
15 Column 1 1 10 00 r[10]=t2.data
16 Rowid 1 11 0 00 r[11]=rowid
17 MakeRecord 10 2 9 00 r[9]=mkrec(r[10..11])
18 SorterInsert 3 9 0 00 key=r[9]
19 Next 1 15 0 00
20 OpenWrite 2 1 0 k(2,,) 11 root=1 iDb=0
21 SorterSort 3 26 0 00
22 SorterData 3 9 2 00 r[9]=data
23 SeekEnd 2 0 0 00
24 IdxInsert 2 9 0 10 key=r[9]
25 SorterNext 3 22 0 00
26 Close 1 0 0 00
27 Close 2 0 0 00
28 Close 3 0 0 00
29 SetCookie 0 1 5 00
30 ParseSchema 0 0 0 name='i1' AND type='index' 00
31 Expire 0 1 0 00
32 Halt 0 0 0 00
33 Transaction 0 1 4 0 01 usesStmtJournal=1
34 Goto 0 1 0 00
先是往sqlite_master表插入新的index的信息。
再可以看到它会遍历所有t2.data，把每条t2的data作为key，t2的rowid作为数据拿出来，排序。
再一个个插入新建的索引b树。这样看，index树和表b树本质是差不多的，都是以一个key确定b树的结构。
只不过表b树用的key是默认的rowid，index树的key是用户指定。如果数据量很大，每个index(对应每棵b树)都会占据很大的空间。在数据量很大的表上操作索引也很耗时。
这和平时使用同类型数据库观察到的现象是一致的。
创建索引后可以explain一些查询，观察b树的使用情况。
用select * from sqlite_master;可以看到数据库所有表和index，和对应的b树。
第一列说明是索引还是表。
第二列是索引或表的名字。
第三列是所在的表名字。
第四列是对应的b树的根页号，对应explain里的root=xxx，这样就能看到用的是哪个b树。
第五列是创建信息。
sqlite> SELECT * FROM sqlite_master;
table|tbl1|tbl1|2|CREATE TABLE tbl1(one varchar(10), two smallint)
table|xcc|xcc|3|CREATE TABLE xcc(id int primary key not null)
index|sqlite_autoindex_xcc_1|xcc|4|
table|sqlite_stat1|sqlite_stat1|5|CREATE TABLE sqlite_stat1(tbl,idx,stat)
table|t2|t2|6|CREATE TABLE t2(id int, data int)
index|i1|t2|8|CREATE INDEX i1 on t2(id)
index|i2|t2|9|CREATE INDEX i2 on t2(id, data)
table|t3|t3|7|CREATE TABLE t3(id int, d1 int, d2 int)
index|t3_i2|t3|10|CREATE INDEX t3_i2 on t3(id, d1)
index|t3_i3|t3|11|CREATE INDEX t3_i3 on t3(id, d1, d2)
对比一下创建index前后，进行数据查找的opcode。
sqlite> explain select * from t2 where data > 1000;
addr opcode p1 p2 p3 p4 p5 comment
---- ------------- ---- ---- ---- ------------- -- -------------
0 Init 0 10 0 00 Start at 10
1 OpenRead 0 6 0 2 00 root=6 iDb=0; t2
2 Rewind 0 9 0 00
3 Column 0 1 1 00 r[1]=t2.data
4 Le 2 8 1 (BINARY) 54 if r[1]<=r[2] goto 8
5 Column 0 0 3 00 r[3]=t2.id
6 Column 0 1 4 00 r[4]=t2.data
7 ResultRow 3 2 0 00 output=r[3..4]
8 Next 0 3 0 01
9 Halt 0 0 0 00
10 Transaction 0 0 4 0 01 usesStmtJournal=0
11 Integer 1000 2 0 00 r[2]=1000
12 Goto 0 1 0 00
可以看到是不断在比较并Next，依次比较cursor的下一个数据，如果<=1000，看下一个数据，否则输出当前数据，再看下个数据。这样是强行遍历所有原始数据来查找。
sqlite> create index i1 on t2(data);
sqlite> explain select * from t2 where data > 1000;
addr opcode p1 p2 p3 p4 p5 comment
---- ------------- ---- ---- ---- ------------- -- -------------
0 Init 0 11 0 00 Start at 11
1 OpenRead 0 6 0 2 00 root=6 iDb=0; t2
2 OpenRead 1 7 0 k(2,,) 00 root=7 iDb=0; i1
3 Integer 1000 1 0 00 r[1]=1000
4 SeekGT 1 10 1 1 00 key=r[1]
5 DeferredSeek 1 0 0 00 Move 0 to 1.rowid if needed
6 Column 0 0 2 00 r[2]=t2.id
7 Column 1 0 3 00 r[3]=t2.data
8 ResultRow 2 2 0 00 output=r[2..3]
9 Next 1 5 0 00
10 Halt 0 0 0 00
11 Transaction 0 0 5 0 01 usesStmtJournal=0
12 Goto 0 1 0 00
创建index后，可见新的index的b树根页号root=7。默认数据表的根页号是6。
搜索用的是index树，效率提高。
联合索引的原理？#
sqlite> explain create index t3_i2 on t3(id, d1);
14 Rewind 1 21 0 00
15 Column 1 0 10 00 r[10]=t3.id
16 Column 1 1 11 00 r[11]=t3.d1
17 Rowid 1 12 0 00 r[12]=rowid
18 MakeRecord 10 3 9 00 r[9]=mkrec(r[10..12])
19 SorterInsert 3 9 0 00 key=r[9]
20 Next 1 15 0 00
单个索引把一个字段组成一条数据插入索引b树。
联合索引把多个字段组成一条数据插入索引b树。多个字段组成数据并不会进行什么特殊处理，只相当于依次排开，使两条数据种的列能依次进行比较。
观察最简单的例子 where d1 > 1000 and id > 9。
可以看到不创建联合索引，而创建单个索引，会走单个索引。
创建联合索引，会走联合索引，但也只会搜一列，再遍历所有结果，比较另一列。
sqlite> explain select * from t3 where d1 > 1000 and id > 9;
addr opcode p1 p2 p3 p4 p5 comment
---- ------------- ---- ---- ---- ------------- -- -------------
0 Init 0 14 0 00 Start at 14
1 OpenRead 0 7 0 3 00 root=7 iDb=0; t3
2 OpenRead 1 10 0 k(3,,,) 00 root=10 iDb=0; t3_i2
3 Integer 9 1 0 00 r[1]=9
4 SeekGT 1 13 1 1 00 key=r[1]
5 DeferredSeek 1 0 0 00 Move 0 to 1.rowid if needed
6 Column 1 1 2 00 r[2]=t3.d1
7 Le 3 12 2 (BINARY) 54 if r[2]<=r[3] goto 12
8 Column 1 0 4 00 r[4]=t3.id
9 Column 1 1 5 00 r[5]=t3.d1
10 Column 0 2 6 00 r[6]=t3.d2
11 ResultRow 4 3 0 00 output=r[4..6]
12 Next 1 5 0 00
13 Halt 0 0 0 00
14 Transaction 0 0 28 0 01 usesStmtJournal=0
15 Integer 1000 3 0 00 r[3]=1000
16 Goto 0 1 0 00
可以看到搜索的key用的是id>9，那么问题来了。只有一棵索引b树，搜了id>9，如何同时用b树搜d1>1000？
结果是做不到，至少不能有效地做到。只能定一些规则，尽量利用索引。
联合索引并不是简单拿几列定义一下就大功告成了。并不能支持随意搜任何列组合。
联合索引是有顺序区分的，查找时会按从左到右的顺序来。
比如create index on t(a, b)，这时如果只查询b是走不了索引的，必须包含a。
因为创建index树时的插入操作就是先比较a，如果a相等再比较b和后面的列。
就像字典一样，必须从左到右依次来查，如果跳过一个字，就属于无脑瞎找。
从代码来看#
排序、创建索引、b树查找数据用的比较函数都是
sqlite3VdbeRecordCompare
sqlite3VdbeRecordCompareWithSkip
依次比较两条数据的列1, 列2, 列3, 列4...
例如创建时按a,b,c三列MakeRecord，按上面的比较函数插入b树。
搜索时可以搜a，ab或abc。只能依次增加，后面可以缺，中间不能跳过，否则不符合插入的比较规则。
总结的一些规则#
(仅限于sqlite。不确定其他同类数据库的情况。不一定完整。比如可能会有b树里再套b树，这样可实现随意查多列。)
对于联合索引(a, b, c):
查找时必须包含a。否则一定不会走联合索引。
包含a的大于或小于查询。
where a < 100 and b > 0 ...;
会以a作为key查b树。再遍历所有查a的结果数据，每条数据判断b或c的情况。
这个情况其实和用单个a的索引相似，区别在于联合索引的key值都在b树节点，可以直接比较。而用单个索引的话，如果需要比较b或c，必须另行读出实际数据，会增加大量磁盘io。包含a的等于查询，且没查b。
where a = 100 and c < 666 and d > 5;
同上，以a作为key查b树，再遍历查其他列。包含a的等于查询，b的大于小于查询。
where a = 100 and b > 0。
以(a, b)作为key查b树。用什么key去查b树很重要，key里包含的信息越多越好。
上一条可以扩展到更多列的联合索引。比如where a = 100 and b = 200 and c > 0会以(a, b, c) 作为key查b树。只要出现依次的等于，就可以把更多的列加到key里。限定越多，就越能利用b树，后续的遍历就会越少。
最好的情况就是每个列都查相等，那就不需要任何遍历，b树一次就能搜到。
所以创建联合索引时，要尽量把查等于的列放左边。