SQLite入门与分析(八)---存储模型(3)

写在前面：接上一节，本节主要讨论索引页面格式，以及索引与查询优化的关系。

(1)索引页面格式
sqlite> select * from sqlite_master;
table|episodes|episodes|2|CREATE TABLE episodes( id integer primary key,name tex
t,cid int)
index|name_index|episodes|3|CREATE INDEX name_index on episodes(name)
第3个页面保存表 episodes的索引(也只占一个页面)。

前8个字节为页面头：
0x0A：leaf+zerodata，表示叶子页面，且页面中只有关键字，没有数据（即索引页面）；
0x0000：表示第一个空闲块的偏移为0；
0x0011：页面的单元数(记录数)，该页面含有17个记录；
0x030D：单元内容区的第一个字节的偏移(距页面起始位置)
0x00： 碎片字节数
接下来34个字节为17个单元（记录）的指针数组。第一个单元的偏移为0x03EC，如

来看看索引单元的格式：
0x13：数据的字节数，19个字节，从0x03开始。
0x03：记录头的字节数。
0x2B：第一个字段的长度，15个字节，该索引是对episodes表的name字段建的，其值为episodes表name字段的值。
0x01：第二个字段的长度，其值为0x01，即episodes表中的对应记录rowid的值。

(2)索引与order by
order by是查询中经常用到的，一些通用DBMS(比如DM，MysqL)都提供基于索引的形式来实现Order by。sqlite也是通过索引来实现Order by的。当字段有索引时，则直接通过索引很容易实现排序；另一方面，如果排序的字段没有索引，则以该字段为索引(这种情况下是聚集索引)建立一张临时表，再将临时表按顺序输出。来看看sqlite的实现吧。

在sqlite中，默认以rowid来建立聚集索引(对于没有整型值主键的情况)。如果主键字段为整型，则将其直接保存在rowid中，实现聚集索引；另一方面，如果主键是字符串，则对主键建立二级索引。非主键的索引都属于二级索引。
先来看看以整型ID为主键的情况：

///////////////以ID(rowid)为索引(即聚集索引)
@H_403_44@sqlite@H_403_44@>@H_403_44@explainselect@H_403_44@*@H_403_44@fromepisodesorderbyid;
0@H_403_44@|@H_403_44@Trace@H_403_44@|0@H_403_44@|0@H_403_44@|@H_403_44@explainselect@H_403_44@*@H_403_44@fromepisodesorderbyid;@H_403_44@|00@H_403_44@|@H_403_44@
1@H_403_44@|@H_403_44@Noop@H_403_44@|0@H_403_44@||2@H_403_44@|@H_403_44@Goto@H_403_44@|13@H_403_44@|3@H_403_44@|@H_403_44@SetNumColumns@H_403_44@|3@H_403_44@|4@H_403_44@|@H_403_44@OpenRead@H_403_44@|2@H_403_44@|00@H_403_44@|@H_403_44@;打开表episodes,p2(@H_403_44@=2@H_403_44@)为其根页面
5@H_403_44@|@H_403_44@Rewind@H_403_44@|11@H_403_44@|00@H_403_44@|@H_403_44@;游标指向第一条记录
6@H_403_44@|@H_403_44@Rowid@H_403_44@|1@H_403_44@|00@H_403_44@|@H_403_44@;取出记录的rowid
7@H_403_44@|@H_403_44@Column@H_403_44@|2@H_403_44@||00@H_403_44@|@H_403_44@;取出第1列的值
8@H_403_44@|@H_403_44@Column@H_403_44@|3@H_403_44@||00@H_403_44@|@H_403_44@;取出第2列的值
9@H_403_44@|@H_403_44@ResultRow@H_403_44@|00@H_403_44@|@H_403_44@;生成记录结果
10@H_403_44@|@H_403_44@Next@H_403_44@|6@H_403_44@|01@H_403_44@|@H_403_44@;取下一条记录
11@H_403_44@|@H_403_44@Close@H_403_44@|12@H_403_44@|@H_403_44@Halt@H_403_44@|13@H_403_44@|@H_403_44@Transaction@H_403_44@|14@H_403_44@|@H_403_44@VerifyCookie@H_403_44@|15@H_403_44@|@H_403_44@TableLock@H_403_44@|0@H_403_44@|@H_403_44@episodes@H_403_44@|16@H_403_44@|@H_403_44@Goto@H_403_44@|00@H_403_44@|

属性有索引的情况：

/////////////排序的实现——有索引
//算法思想:
(1)从索引中依次读取记录(索引记录的形式如:原索引属性-rowid的键值),并取出rowid.
(2)根据(1)中取出的rowid,在原表中查找记录,并生成记录结果.
@H_403_44@sqlite@H_403_44@>@H_403_44@explainselect@H_403_44@*@H_403_44@fromepisodesorderbyname;
0@H_403_44@|@H_403_44@explainselect@H_403_44@*@H_403_44@fromepisodesorderbyname;@H_403_44@|18@H_403_44@|00@H_403_44@|@H_403_44@;打开表,p1为表游标(0@H_403_44@),p2为表根页面
5@H_403_44@|@H_403_44@SetNumColumns@H_403_44@|6@H_403_44@|@H_403_44@OpenRead@H_403_44@|0@H_403_44@|@H_403_44@keyinfo(1@H_403_44@,BINARY)@H_403_44@|00@H_403_44@|@H_403_44@;打开索引,p1为索引游标,p2为根页面
7@H_403_44@|@H_403_44@Rewind@H_403_44@|15@H_403_44@|8@H_403_44@|@H_403_44@IdxRowid@H_403_44@|00@H_403_44@|@H_403_44@;从索引记录中取出rowid
9@H_403_44@|@H_403_44@Seek@H_403_44@|00@H_403_44@|@H_403_44@;根据rowid从表中查找记录
10@H_403_44@|@H_403_44@IdxRowid@H_403_44@|11@H_403_44@|@H_403_44@Column@H_403_44@|12@H_403_44@|@H_403_44@Column@H_403_44@|4@H_403_44@||13@H_403_44@|@H_403_44@ResultRow@H_403_44@|14@H_403_44@|@H_403_44@Next@H_403_44@|8@H_403_44@|15@H_403_44@|@H_403_44@Close@H_403_44@|16@H_403_44@|@H_403_44@Close@H_403_44@|17@H_403_44@|@H_403_44@Halt@H_403_44@|18@H_403_44@|@H_403_44@Transaction@H_403_44@|19@H_403_44@|@H_403_44@VerifyCookie@H_403_44@|20@H_403_44@|@H_403_44@TableLock@H_403_44@|21@H_403_44@|@H_403_44@Goto@H_403_44@|
对于没有索引的属性排序：

@H_403_44@////////////////排序的实现——没有索引
 //(1@H_403_44@)按查询属性为聚集索引建立一个临时表;
 @H_403_44@//(2@H_403_44@)按索引顺序输出结果。
 sqlite>explainselect*fromepisodesorderbycid;
 0@H_403_44@|Trace|0@H_403_44@|explainselect*fromepisodesorderbycid;|00|
 1@H_403_44@|OpenEphemeral|0@H_403_44@|keyinfo(00@H_403_44@|p1为临时表游标,p2为临时表列数2@H_403_44@|Goto|30@H_403_44@|00@H_403_44@|
 3@H_403_44@|SetNumColumns|4@H_403_44@|OpenRead|打开表episodes5@H_403_44@|Rewind|16@H_403_44@|游标移到表的第1条记录,p1为游标下标6@H_403_44@|Rowid|p1为表的下标,p2指向表的记录7@H_403_44@|Column|读取表p1(=0)的第1列8@H_403_44@|Column|读取表p1(=0)的第2列9@H_403_44@|MakeRecord|10@H_403_44@|SCopy|5@H_403_44@|11@H_403_44@|Sequence|12@H_403_44@|Move|4@H_403_44@|7@H_403_44@|1@H_403_44@||13@H_403_44@|MakeRecord|8@H_403_44@||14@H_403_44@|IdxInsert|该指令在索引中插入记录,相当于对表的Insert.p1为索引下标,即OpenEphemeral打开的临时表15@H_403_44@|Next|01@H_403_44@|
 16@H_403_44@|Close|关闭表episodes17@H_403_44@|SetNumColumns|18@H_403_44@|OpenPseudo|打开临时表19@H_403_44@|Sort|28@H_403_44@|与Rewind功能类似20@H_403_44@|Column|21@H_403_44@|Integer|22@H_403_44@|Insert|23@H_403_44@|Column|24@H_403_44@|Column|25@H_403_44@|Column|26@H_403_44@|ResultRow|输出临时记录27@H_403_44@|Next|20@H_403_44@|28@H_403_44@|Close|29@H_403_44@|Halt|30@H_403_44@|Transaction|31@H_403_44@|VerifyCookie|32@H_403_44@|TableLock|0@H_403_44@|episodes|33@H_403_44@|Goto|00@H_403_44@|