写在前面:接上一节,本节主要讨论索引页面格式,以及索引与查询优化的关系。
(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为主键的情况:
属性有索引的情况:
(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_41@
sqlite>explainselect*fromepisodesorderbyid;
@H_403_41@0|Trace|@H_403_41@0|@H_403_41@0|explainselect*fromepisodesorderbyid;|@H_403_41@00|
@H_403_41@1|Noop|@H_403_41@0||@H_403_41@2|Goto|@H_403_41@13|@H_403_41@3|SetNumColumns|@H_403_41@3|@H_403_41@4|OpenRead|@H_403_41@2|@H_403_41@00|;打开表episodes,p2(=@H_403_41@2)为其根页面
@H_403_41@5|Rewind|@H_403_41@11|@H_403_41@00|;游标指向第一条记录
@H_403_41@6|Rowid|@H_403_41@1|@H_403_41@00|;取出记录的rowid
@H_403_41@7|Column|@H_403_41@2||@H_403_41@00|;取出第1列的值
@H_403_41@8|Column|@H_403_41@3||@H_403_41@00|;取出第2列的值
@H_403_41@9|ResultRow|@H_403_41@00|;生成记录结果
@H_403_41@10|Next|@H_403_41@6|@H_403_41@01|;取下一条记录
@H_403_41@11|Close|@H_403_41@12|Halt|@H_403_41@13|Transaction|@H_403_41@14|VerifyCookie|@H_403_41@15|TableLock|@H_403_41@0|episodes|@H_403_41@16|Goto|@H_403_41@00|
sqlite>explainselect*fromepisodesorderbyid;
@H_403_41@0|Trace|@H_403_41@0|@H_403_41@0|explainselect*fromepisodesorderbyid;|@H_403_41@00|
@H_403_41@1|Noop|@H_403_41@0||@H_403_41@2|Goto|@H_403_41@13|@H_403_41@3|SetNumColumns|@H_403_41@3|@H_403_41@4|OpenRead|@H_403_41@2|@H_403_41@00|;打开表episodes,p2(=@H_403_41@2)为其根页面
@H_403_41@5|Rewind|@H_403_41@11|@H_403_41@00|;游标指向第一条记录
@H_403_41@6|Rowid|@H_403_41@1|@H_403_41@00|;取出记录的rowid
@H_403_41@7|Column|@H_403_41@2||@H_403_41@00|;取出第1列的值
@H_403_41@8|Column|@H_403_41@3||@H_403_41@00|;取出第2列的值
@H_403_41@9|ResultRow|@H_403_41@00|;生成记录结果
@H_403_41@10|Next|@H_403_41@6|@H_403_41@01|;取下一条记录
@H_403_41@11|Close|@H_403_41@12|Halt|@H_403_41@13|Transaction|@H_403_41@14|VerifyCookie|@H_403_41@15|TableLock|@H_403_41@0|episodes|@H_403_41@16|Goto|@H_403_41@00|
属性有索引的情况:
/////////////排序的实现——有索引@H_403_41@
//算法思想:
(1)从索引中依次读取记录(索引记录的形式如:原索引属性-rowid的键值),并取出rowid.
(2)根据(1)中取出的rowid,在原表中查找记录,并生成记录结果.
sqlite>explainselect*fromepisodesorderbyname;
@H_403_41@0|explainselect*fromepisodesorderbyname;|@H_403_41@18|@H_403_41@00|;打开表,p1为表游标(@H_403_41@0),p2为表根页面
@H_403_41@5|SetNumColumns|@H_403_41@6|OpenRead|@H_403_41@0|keyinfo(@H_403_41@1,BINARY)|@H_403_41@00|;打开索引,p1为索引游标,p2为根页面
@H_403_41@7|Rewind|@H_403_41@15|@H_403_41@8|IdxRowid|@H_403_41@00|;从索引记录中取出rowid
@H_403_41@9|Seek|@H_403_41@00|;根据rowid从表中查找记录
@H_403_41@10|IdxRowid|@H_403_41@11|Column|@H_403_41@12|Column|@H_403_41@4||@H_403_41@13|ResultRow|@H_403_41@14|Next|@H_403_41@8|@H_403_41@15|Close|@H_403_41@16|Close|@H_403_41@17|Halt|@H_403_41@18|Transaction|@H_403_41@19|VerifyCookie|@H_403_41@20|TableLock|@H_403_41@21|Goto|
对于没有索引的属性排序:
//算法思想:
(1)从索引中依次读取记录(索引记录的形式如:原索引属性-rowid的键值),并取出rowid.
(2)根据(1)中取出的rowid,在原表中查找记录,并生成记录结果.
sqlite>explainselect*fromepisodesorderbyname;
@H_403_41@0|explainselect*fromepisodesorderbyname;|@H_403_41@18|@H_403_41@00|;打开表,p1为表游标(@H_403_41@0),p2为表根页面
@H_403_41@5|SetNumColumns|@H_403_41@6|OpenRead|@H_403_41@0|keyinfo(@H_403_41@1,BINARY)|@H_403_41@00|;打开索引,p1为索引游标,p2为根页面
@H_403_41@7|Rewind|@H_403_41@15|@H_403_41@8|IdxRowid|@H_403_41@00|;从索引记录中取出rowid
@H_403_41@9|Seek|@H_403_41@00|;根据rowid从表中查找记录
@H_403_41@10|IdxRowid|@H_403_41@11|Column|@H_403_41@12|Column|@H_403_41@4||@H_403_41@13|ResultRow|@H_403_41@14|Next|@H_403_41@8|@H_403_41@15|Close|@H_403_41@16|Close|@H_403_41@17|Halt|@H_403_41@18|Transaction|@H_403_41@19|VerifyCookie|@H_403_41@20|TableLock|@H_403_41@21|Goto|
对于没有索引的属性排序:
////////////////排序的实现——没有索引
//(@H_403_41@1)按查询属性为聚集索引建立一个临时表;
//(@H_403_41@2)按索引顺序输出结果。
sqlite>explainselect*fromepisodesorderbycid;
@H_403_41@0|Trace|@H_403_41@0|explainselect*fromepisodesorderbycid;|00|
@H_403_41@1|OpenEphemeral|@H_403_41@0|keyinfo(403_41@00|p1为临时表游标,p2为临时表列数2|Goto|@H_403_41@30|@H_403_41@00|
@H_403_41@3|SetNumColumns|@H_403_41@4|OpenRead|打开表episodes5|Rewind|@H_403_41@16|游标移到表的第1条记录,p1为游标下标6|Rowid|p1为表的下标,p2指向表的记录7|Column|读取表p1(=0)的第1列8|Column|读取表p1(=0)的第2列9|MakeRecord|@H_403_41@10|SCopy|@H_403_41@5|@H_403_41@11|Sequence|@H_403_41@12|Move|@H_403_41@4|@H_403_41@7|@H_403_41@1||@H_403_41@13|MakeRecord|@H_403_41@8||@H_403_41@14|IdxInsert|该指令在索引中插入记录,相当于对表的Insert.p1为索引下标,即OpenEphemeral打开的临时表15|Next|@H_403_41@01|
@H_403_41@16|Close|关闭表episodes17|SetNumColumns|@H_403_41@18|OpenPseudo|打开临时表19|Sort|@H_403_41@28|与Rewind功能类似20|Column|@H_403_41@21|Integer|@H_403_41@22|Insert|@H_403_41@23|Column|@H_403_41@24|Column|@H_403_41@25|Column|@H_403_41@26|ResultRow|输出临时记录27|Next|@H_403_41@20|@H_403_41@28|Close|@H_403_41@29|Halt|@H_403_41@30|Transaction|@H_403_41@31|VerifyCookie|@H_403_41@32|TableLock|@H_403_41@0|episodes|@H_403_41@33|Goto|@H_403_41@00|
//(@H_403_41@1)按查询属性为聚集索引建立一个临时表;
//(@H_403_41@2)按索引顺序输出结果。
sqlite>explainselect*fromepisodesorderbycid;
@H_403_41@0|Trace|@H_403_41@0|explainselect*fromepisodesorderbycid;|00|
@H_403_41@1|OpenEphemeral|@H_403_41@0|keyinfo(403_41@00|p1为临时表游标,p2为临时表列数2|Goto|@H_403_41@30|@H_403_41@00|
@H_403_41@3|SetNumColumns|@H_403_41@4|OpenRead|打开表episodes5|Rewind|@H_403_41@16|游标移到表的第1条记录,p1为游标下标6|Rowid|p1为表的下标,p2指向表的记录7|Column|读取表p1(=0)的第1列8|Column|读取表p1(=0)的第2列9|MakeRecord|@H_403_41@10|SCopy|@H_403_41@5|@H_403_41@11|Sequence|@H_403_41@12|Move|@H_403_41@4|@H_403_41@7|@H_403_41@1||@H_403_41@13|MakeRecord|@H_403_41@8||@H_403_41@14|IdxInsert|该指令在索引中插入记录,相当于对表的Insert.p1为索引下标,即OpenEphemeral打开的临时表15|Next|@H_403_41@01|
@H_403_41@16|Close|关闭表episodes17|SetNumColumns|@H_403_41@18|OpenPseudo|打开临时表19|Sort|@H_403_41@28|与Rewind功能类似20|Column|@H_403_41@21|Integer|@H_403_41@22|Insert|@H_403_41@23|Column|@H_403_41@24|Column|@H_403_41@25|Column|@H_403_41@26|ResultRow|输出临时记录27|Next|@H_403_41@20|@H_403_41@28|Close|@H_403_41@29|Halt|@H_403_41@30|Transaction|@H_403_41@31|VerifyCookie|@H_403_41@32|TableLock|@H_403_41@0|episodes|@H_403_41@33|Goto|@H_403_41@00|