SQLite学习笔记（15）-B-tree（1）

Sqlite 前端之家
前端之家收集整理的这篇文章主要介绍了SQLite学习笔记（15）-B-tree（1），前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。

B-Tree

B-tree的主要功能就是索引，它维护着各个页面之间的复杂的关系，便于快速找到所需数据。

B-Tree使得VDBE可以在O(logN)下查询，插入和删除数据，以及O(1)下双向遍历结果集。B-Tree不会直接读写磁盘，它仅仅维护着页面 (pages)之间的关系。当B-TREE需要页面或者修改页面时，它就会调用Pager。当修改页面时，pager保证原始页面首先写入日志文件，当它完成写操作时，pager根据事务状态决定如何做。B-tree不直接读写文件，而是通过page cache这个缓冲模块读写文件对于性能是有重要意义的。

2.5.1 数据库文件格式（DatabaseFile Format）

从逻辑上来说，一个sqlite数据库文件由多个多重Btree构成。一个数据库由许多B-tree构成——每一个表和索引都有一个B-tree（注：索引采用B-tree，而表采用B+tree，这主要是表和索引的需求不同以及B-tree和B+tree的结构不同决定的：B+tree的所有叶子节点包含了全部关键字信息，而且可以有两种顺序查找。而B-tree更适合用来作索引）。

2.5.1.1 页

数据库文件包括一个或多个页。页的大小可以是512B到64KB之间的2的任意次方。

数据库中所有的页面都按从1开始顺序标记，其最大页数目为2147483646 ( - 2)[6]。数据库中的页主要分为以下几类：

  • The lock-byte page
  • A freelist page
    • A freelist trunk page
    • A freelist leaf page
  • A b-tree page
    • A table b-tree interior page
    • A table b-tree leaf page
    • An index b-tree interior page
    • An index b-tree leaf page
  • A payload overflow page
  • A pointer map page

数据库中加载到内存中的页的定义位于btreeInt.h，其结构如下：

<pre name="code" class="cpp">structMemPage {
  u8 isInit;           /* True if prevIoUsly initialized.MUST BE FIRST! */
  u8 nOverflow;        /* Number of overflow cell bodies inaCell[] */
  u8 intKey;           /* True if table b-trees.  False for index b-trees */
  u8 intKeyLeaf;       /* True if the leaf of an intKey table*/
  u8 noPayload;        /* True if internal intKey page (thusw/o data) */
  u8 leaf;             /* True if a leaf page */
  u8 hdrOffset;        /* 100 for page 1.  0 otherwise */
  u8 childPtrSize;     /* 0 if leaf==1.  4 if leaf==0 */
  u8 max1bytePayload;  /* min(maxLocal,127) */
  u8 bBusy;            /* Prevent endless loops on corruptdatabase files */
  u16 maxLocal;        /* Copy of BtShared.maxLocal orBtShared.maxLeaf */
  u16 minLocal;        /* Copy of BtShared.minLocal orBtShared.minLeaf */
  u16 cellOffset;      /* Index in aData of first cell pointer*/
  u16 nFree;           /* Number of free bytes on the page*/
  u16 nCell;           /* Number of cells on this page,local and ovfl */
  u16 maskPage;        /* Mask for page offset */
  u16 aiOvfl[5];       /* Insert the i-th overflow cell beforethe aiOvfl-th
                       ** non-overflow cell */
  u8 *apOvfl[5];       /* Pointers to the body of overflowcells */
  BtShared *pBt;       /* Pointer to BtShared that this page ispart of */
  u8 *aData;           /* Pointer to disk image of the page data */
  u8 *aDataEnd;        /* One byte past the end of usable data*/
  u8 *aCellIdx;        /* The cell index area */
  u8 *aDataOfst;       /* Same as aData for leaves.  aData+4 for interior */
  DbPage *pDbPage;     /* Pager page handle */
  u16 (*xCellSize)(MemPage*,u8*);             /* cellSizePtr method */
  void (*xParseCell)(MemPage*,u8*,CellInfo*);/* btreeParseCell method */
  Pgno pgno;           /* Page number for this page */
};
 
 

2.5.1.2 文件头
 

数据库中第一个页(page 1)永远是Btree页。而每个表或索引的第1个页称为根页，所有表或索引的根页编号都存储在系统表sqlite_master中，表sqlite_master的根页为page 1。Page 1的前100个字节是一个对数据库文件进行描述的“文件头”。它包括数据库的版本、格式的版本、页大小、编码等所有创建数据库时设置的永久性参数。这个特殊文件头的文档在btreeInt.h中，格式如表2.2所示。
 

表2.2 Page 1的前100字节
 
 
@H_41_403@ 

2.5.1.3 锁字节页（TheLock-Byte Page）
锁字节页是数据库文件中的单独一页，它包含偏移量在1073741824和1073742335字节之间的字节。不大于1073741824字节的数据库文件没有锁字节页。只有大于1073741824字节的数据库文件含有一页锁字节页。
sqlite不使用锁字节页，它是专门留给OS在VFS实现中的数据库文件锁定原语。
锁字节页定义在btreeInt.h，其结构如下：
structBtLock {
  Btree *pBtree;        /* Btree handle holding this lock */
  Pgno iTable;          /* Root page of table */
  u8 eLock;             /* READ_LOCK or WRITE_LOCK *
  BtLock *pNext;        /* Next in BtShared.pLock list */
};
2.5.1.4 空闲页链表（TheFreelist）
一个数据库文件或多或少含有一些没有使用的页。这些页可能是由于其中的信息被数据库删除产生的。这些空闲页被存放在空闲页链表，当需要额外的页时就会被重用。
空闲页链表是由freelist trunkpage相互连接组成的链表，而每个freelist trunk page是由freelist leaf page（可以为零）组成的。
一个freelist trunk page是由一个4字节大端整数数组组成。数组是在可用空间中放入尽可能多的整数。它的最小可用空间是480字节，所以数组最少可以放120整数。数组中的第一个整数指向链表中的下一个freelist trunk page，如果为零就代表这是链表中的最后一个freelist trunk page。第二个整数代表所含有的freelist leaf page指针的数目。将第二个整数称为L，如果L大于零，那么数组中2到L+1之间的每个整数就表示一个freelist leaf page。
在freelist leaf page中则什么都没有。
2.5.1.5 B-tree页（B-treePages）
sqlite中使用了两种B-tree。其中一种是b+tree，将所用的数据存储在叶子节点，在sqlite中被称为table b-tree。另一种是最初未经修改的b-tree，枝干节点和叶子节点都含有关键字和数据，在sqlite中被称为index b-tree。
Btree页内部以单元为单位来组织数据，一个单元包含一个(或部分，当使用溢出页时)payload(也称为Btree记录)。由于各类数据大小各不相同，每个单元的大小也就是可变的，所以Btree页内部的空间需要进行动态分配(程序内部动态分配，不是动态申请空间)，单元是Btree页内部进行空间分配和回收的基本单位。每一个Btree页包括三个部分：页头，单元指针数组以及单元内容区。Page1除包括页头外，还包括100字节的文件头，其结构如图2.6所示。页内所有单元的内容集中在页的底部，称为“单元内容区”，由下向上增长。而单元指针数组则含有单元内容区每个单元的偏移量（2 byte），顺序排列，偏于对单元内容进行插入和查找，由上而下增长。
 
 
 
  
  
 
    
偏移量
 		 
    
大小
 		 
    
说明
 		 
  
 
  
 
    
0
 		 
    
16
 		 
    
The header string: "sqlite format 3\000"
 		 
  
 
  
 
    
16
 		 
    
2
 		 
    
The database page size in bytes. Must be a power of two between 512 and 65536. 
 		 
  
 
  
 
    
18
 		 
    
1
 		 
    
File format write version. 1 for legacy; 2 forWAL.
 		 
  
 
  
 
    
19
 		 
    
1
 		 
    
File format read version. 1 for legacy; 2 forWAL.
 		 
  
 
  
 
    
20
 		 
    
1
 		 
    
Bytes of unused "reserved" space at the end of each page. Usually 0.
 		 
  
 
  
 
    
21
 		 
    
1
 		 
    
Maximum embedded payload fraction. Must be 64.
 		 
  
 
  
 
    
22
 		 
    
1
 		 
    
Minimum embedded payload fraction. Must be 32.
 		 
  
 
  
 
    
23
 		 
    
1
 		 
    
Leaf payload fraction. Must be 32.
 		 
  
 
  
 
    
24
 		 
    
4
 		 
    
File change counter.
 		 
  
 
  
 
    
28
 		 
    
4
 		 
    
Size of the database file in pages. The "in-header database size".
 		 
  
 
  
 
    
32
 		 
    
4
 		 
    
Page number of the first freelist trunk page.
 		 
  
 
  
 
    
36
 		 
    
4
 		 
    
Total number of freelist pages.
 		 
  
 
  
 
    
40
 		 
    
4
 		 
    
The schema cookie.
 		 
  
 
  
 
    
44
 		 
    
4
 		 
    
The schema format number. Supported schema formats are 1,2,3,and 4.
 		 
  
 
  
 
    
48
 		 
    
4
 		 
    
Default page cache size.
 		 
  
 
  
 
    
52
 		 
    
4
 		 
    
The page number of the largest root b-tree page when in auto-vacuum or incremental-vacuum modes,or zero otherwise.
 		 
  
 
  
 
    
56
 		 
    
4
 		 
    
The database text encoding. A value of 1 means UTF-8. A value of 2 means UTF-16le. A value of 3 means UTF-16be.
 		 
  
 
  
 
    
60
 		 
    
4
 		 
    
The "user version" as read and set by theuser_version pragma.
 		 
  
 
  
 
    
64
 		 
    
4
 		 
    
True (non-zero) for incremental-vacuum mode. False (zero) otherwise.
 		 
  
 
  
 
    
68
 		 
    
4
 		 
    
The "Application ID" set byPRAGMA application_id.
 		 
  
 
  
 
    
72
 		 
    
20
 		 
    
Reserved for expansion. Must be zero.
 		 
  
 
  
 
    
92
 		 
    
4
 		 
    
Theversion-valid-for number.
 		 
  
 
  
 
    
96
 		 
    
4
 		 
    
SQLITE_VERSION_NUMBER
 		 
  
 
  
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 
 @H_41_403@ 

图2.6 Btree页结构
其页头格式如表2.3所示。其中Flags定义了Btree页的类型。标识leaf表示这个也是否有孩子。标识zerodata表示这个页只有记录没有数据。标识intkey表示整数关键字存放在key size entry，而不是payload区域。
表2.3 Btree页头格式
 
   
   
 
     
文件头（只有page 1有）
 		 
   
 
   
 
     
页头
 		 
   
 
   
 
     
单元指针数组
 		 
   
 
   
 
     
未分配空间
 		 
   
 
   
 
     
单元内容区
 		 
   
 
   
 
 
 

 
@H_41_403@ 

Flags可以表示四种类型的Btree页，其值如下：
Ø 如果是B+tree的叶子页，该字节值为0X0D，
Ø 如果是B+tree的内部页，该字节值为0X05，
Ø 如果是B-tree的叶子页，该字节值为0X0A，
Ø 如果是B-tree的内部页，该字节值为0X02。
而这四种Btree页的单元格式如表2.4所示。
表2.4 Btree页单元格式
 
  
  
 
    
偏移量
 		 
    
大小
 		 
    
说明
 		 
  
 
  
 
    
0 
 		 
    
1 
 		 
    
Flags. 1: intkey,2: zerodata,4: leafdata,8: leaf
 		 
  
 
  
 
    
1 
 		 
    
2 
 		 
    
byte offset to the first freeblock
 		 
  
 
  
 
    
3 
 		 
    
2 
 		 
    
number of cells on this page
 		 
  
 
  
 
    
5 
 		 
    
2 
 		 
    
first byte of the cell content area
 		 
  
 
  
 
    
7 
 		 
    
1 
 		 
    
number of fragmented free bytes
 		 
  
 
  
 
    
8 
 		 
    
4 
 		 
    
Right child (the Ptr(N) value). Omitted on leaves.
 		 
  
 
  
 
 
 
 
 
 

 
@H_41_403@ 

2.5.1.6 Cell Payload OverflowPages
当btree页的一个btree单元的payload太大时，超出的部分机会放入溢出页。这些溢出页会形成一个链表。每个溢出页的前四个字节都是大端整数，指的是在链表上下一页的页码，不过如果为零的话就是指它是最后一页。之后的有效字节都是用来保存溢出内容。其结构如图2.7所示。
 
图2.7 溢出页
2.5.1.7 Pointer Map or PtrmapPages
Pointer map或者ptrmap页都是额外插入数据库用来使auto_vacuum和incremental_vacuum操作更加高效的附加页。
数据库中其他的页都是从从双亲节点指向孩子节点，而ptrmap页正好相反。
 原文链接：https://www.f2er.com/sqlite/199369.html

            

              




            

          

            

              

                  
    
猜你在找的Sqlite相关文章



                                    
SQLite学习笔记

                                
安装 在Windows上安装SQLite。 访问官网下载下Precompliled Binaries for Windows的两个压...

                                
                                
                            



                                    
windows上如何安装Sqlite

                                
一、安装 下载地址：http://www.sqlite.org/download.html 将Precompiled Binaries for Wi...

                                
                                
                            



                                    
【Android数据存储】SQLite使用实例(附源码)

                                
实例: 会员信息管理 功能：1.查看数据库 2.清空数据库 3.增加会员 4.删除会员 5.更新会员 ...

                                
                                
                            



                                    
SQLite数据库管理

                                

                                
                                
                            



                                    
SQLite3常用命令

                                

                                
                                
                            







                                    
加密你的SQLite

                                
关于SQLite SQLite是一个轻量的、跨平台的、开源的数据库引擎，它的在读写效率、消耗总量、...

                                
                                
                            



                                    
SQLite这么娇小可爱，不多了解点都不行啊

                                
在我眼里，MySQL和Oracle是这样的 而SQLite在是这样的 所以这么萌的数据库，我真的应该多了...

                                
                                
                            



                                    
SQLite这么娇小可爱，不多了解点都不行啊

                                
在我眼里，MySQL和Oracle是这样的 而SQLite在是这样的 所以这么萌的数据库，我真的应该多了...

                                
                                
                            



                                    
SQLite 这么娇小可爱，不多了解点都不行啊

                                
（点击上方蓝字，快速关注我们) 作者：空之境界 网址：http://supermao.cn/sqlitezhe-yao-...

                                
                                
                            



                                    
SQLITE3 使用总结

                                
SQLITE3 使用总结 投稿：hebedich 字体：[ 增加  减小] 类型：转载 时间：2014-08-19 Sql...

                                
                                
                            







            

          

          
          

            

              

                
                
MySQLMsSQLOracleSqlitePostgre SQLMariadbMongoDBNoSQLHBaseJDBC

                

              

            

          

          
         
          

            

              
 



              

            

          

          
          
          
          

            

              

                
                
              

            

          

          


          
          

            

              

                
                
undo日志persistent-cmysql-error-postal-codesql-match-almysql-5.6mysql-8.0database-tri安装路径系统错误data_dir丢失文件主从同步sql_mode数据库目录匿名用户character_seID归零数据库位置查询表重复字段查询字段截断日志SUSPECT7391Remote ServeLinked Serve玄学问题登录不上开启远程访问

              

            

          

          
          
          
         
          

            

              
 



              

            

          

          
          
          
 
  
  
 
    
数据类型
 		 
    
Appears in...
 		 
    
说明
 		 
  
 
  
 
    
Table Leaf (0x0d)
 		 
    
Table Interior (0x05)
 		 
    
Index Leaf (0x0a)
 		 
    
Index Interior (0x02)
 		 
  
 
  
 
    
4-byte integer
 		 
    
 		 
    
✔
 		 
    
 		 
    
✔
 		 
    
Page number of left child
 		 
  
 
  
 
    
varint
 		 
    
✔
 		 
    
 		 
    
✔
 		 
    
✔
 		 
    
Number of bytes of payload
 		 
  
 
  
 
    
varint
 		 
    
✔
 		 
    
✔
 		 
    
 		 
    
 		 
    
Rowid
 		 
  
 
  
 
    
byte array
 		 
    
✔
 		 
    
 		 
    
✔
 		 
    
✔
 		 
    
Payload
 		 
  
 
  
 
    
4-byte integer
 		 
    
✔
 		 
    
 		 
    
✔
 		 
    
✔
 		 
    
Page number of first overflow page