SQLite 存储模型(2)

分手后的思念是犯贱 2022-07-26 12:21 170阅读 0赞

写在前面：接上一节，本节主要讨论索引页面格式，以及索引与查询优化的关系。  
  
(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的索引(也只占一个页面)。  
![sqlite_8_3_1.JPG][]  
前8个字节为页面头：  
0x0A：leaf+zerodata，表示叶子页面，且页面中只有关键字，没有数据（即索引页面）；  
0x0000：表示第一个空闲块的偏移为0；  
0x0011：页面的单元数(记录数)，该页面含有17个记录；  
0x030D：单元内容区的第一个字节的偏移(距页面起始位置)  
0x00： 碎片字节数  
接下来34个字节为17个单元（记录）的指针数组。第一个单元的偏移为0x03EC，如  
![sqlite_8_3_2.JPG][]  
来看看索引单元的格式：  
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为主键的情况：

![复制代码][copycode.gif]

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

![复制代码][copycode.gif]

属性有索引的情况：

![复制代码][copycode.gif]

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

![复制代码][copycode.gif]

对于没有索引的属性排序：

![复制代码][copycode.gif]

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

![复制代码][copycode.gif]

[sqlite_8_3_1.JPG]: /images/20220724/082b962ecb0f451193eb176c9516fb44.png
[sqlite_8_3_2.JPG]: /images/20220724/b3199e1ab8da4e2ab343ce980706f2c3.png
[copycode.gif]: /images/20220724/3dd37e91794c427396a3dccb4affb999.png