的效率下双向遍历-脚本编程之：perl语言入门(第五版中文版)下载

B-tree 使 VDBE执行查找、插入和删除的效率达到 O(logN)，以及在O(1)的效率下双向遍历 结果集。它是自平衡的，可自动地执行碎片整理和空间回收。B-tree本身不会直接读写磁盘， 它仅仅维护着页(page)之间的关系。当B-tree 需要页或者修改页时，它就会调用 pager。当修 改页时，pager保证原始页首先写入日志文件。当它完成写操作时，pager根据事务状态决定 如何做。 数据库文件格式 数据库中所有的页从 1 开始顺序编号。一个数据库由多个多重 B-tree 构成——B-tree 用于每 一个表和索引。每个表和索引的第 1个页(地址)称为根页。所有表和索引的根页都存储在 sqlite_master 表中。 数据库中第一个页(page 1)有点特殊，page 1的前 100个字节是一个对数据库文件进行描述 的特殊文件头。它包括库的版本、格式的版本、页大小、编码等所有创建数据库时设置的永久 性参数。有关这个特殊文件头的文档在 btree.c中，page 1也是 sqlite_master 表的根页。 页重用及回收 SQLite 利用一个空闲页链表(free list)完成页的循环使用。当一个页的所有记录都被删除时， 就被插入到该链表。当有新信息需要进入数据库时，临近的空闲页先被选中，当没有空闲页 时，才创建新的页(会增加文件的大小)。当运行VACUUM命令时，会清空空闲页链表，所 以数据库会缩小。本质上它是在新的文件中重新建立数据库，而所正使用的页都被拷贝过去， 而空闲页链表不拷，结果就是一个新的，变小了的数据库。当数据库的 autovacuum 开启时， SQLite不会使用空闲页链表，而且在每一次事务提交时自动压缩数据库。 B-Tree 记录 B-tree中的页由 B-tree记录组成，也叫做 payload(有效载荷)。每一个B-tree记录(或 payload) 有两个域：关键字域(key field)和数据域(data field)。关键字域就是 ROWID的值，也就是每 个数据库表都会提供的关键字的值。从 B-tree的角度，数据域可以是任何无结构的数据。数 据库的记录就保存在这些数据域中。B-tree的任务就是排序和遍历，这仅需要关键字段 。 Payload的大小是不定的，这与内部的关键字和数据域有关。平均情况下，每个页一般包含 多个 payload，当然也可能一个 payload占用几个页(当一个 payload太大不能存在一个页内)。 112