UP | HOME

SQLite 架构

Table of Contents

SQLite拥有一个精致的、模块化的体系结构,并引进了一些独特的方法进行关系型数据库的管理。它由被组织在 3个子系统 中的 8个独立的模块 组成,这些模块又被分割为两个部分: 前端解析 系统和 后端引擎 ,如图所示:

2.jpg

这个模型将查询过程划分为几个不连续的任务,就像在流水线上工作一样

在体系结构栈的顶部编译查询语句,在中部执行它,在底部处理操作系统的存储和接口

体系结构

在内部,SQLite由以下几个组件组成:内核、SQL编译器、后端以及附件

  • SQLite通过利用 虚拟机和虚拟数据库引擎 VDBE ,使调试、修改和扩展SQLite的内核变得更加方便
    • 所有SQL语句都被编译成易读的、可以在SQLite虚拟机中执行的程序集
  • SQLite支持大小高达2 TB的数据库,每个数据库完全存储在单个磁盘文件中
    • 这些磁盘文件可以在不同字节顺序的计算机之间移动
    • 这些数据以B+树(B+tree)数据结构的形式存储在磁盘上
    • SQLite根据该文件系统获得其数据库权限

SQLite的体系结构图,如图所示:

img1-1.jpg

公共接口Interface

SQLite库的大部分公共接口由 main.c , legacy.c 和 vdbeapi.c 源文件中的函数来实现,这些函数依赖于分散在其他文件中的一些程序,因为在这些文件中它们可以访问有文件作用域的数据结构

词法分析器Tokenizer

当执行一个包含SQL语句的字符串时,接口程序要把这个字符串传递给 tokenizer

  • Tokenizer的任务是把原有字符串分割成一个个 标识符 token
  • 把这些标识符传递给解析器

Tokenizer是用手工编写的,在C文件 tokenize.c 中

语法分析器Parser

语法分析器的工作是在指定的上下文中赋予标识符具体的含义。SQLite的 语法分析器 使用 Lemon LALR(1) 分析程序生成器来产生

  • Lemon做的工作与YACC/BISON相同,但它使用不同的输入句法,这种句法更不易出错
  • Lemon还产生可重入的并且线程安全的语法分析器
  • Lemon定义了非终结析构器的概念,当遇到语法错误时它不会泄露内存

驱动Lemon的源文件可在 parse.y 中找到

代码生成器Code Generator

语法分析器在把标识符组装成完整的SQL语句后,就调用代码生成器产生虚拟机代码,以执行SQL语句请求的工作。代码生成器包含许多文件:

  • attach.c
  • auth.c
  • build.c
  • delete.c
  • expr.c
  • insert.c
  • pragma.c
  • select.c
  • trigger.c
  • update.c
  • vacuum.c
  • where.c

这些文件涵盖了大部分最重要、最有意义的事情

  1. expr.c处理SQL中表达式的代码生成
  2. where.c处理SELECT、UPDATE和DELETE语句中WHERE子句的代码生成
  3. attach.c, delete.c, insert.c, select.c, trigger.c, update.c和vacuum.c处理同名SQL语句的代码生成(这些文件在必要时都调用expr.c和where.c中的例程)
  4. 所有其他SQL语句的代码由build.c生成。文件auth.c实现sqlite3_set_authorizer()的功能

虚拟机Virtual Machine

代码生成器生成的代码由虚拟机来执行。总的来说,虚拟机实现一个专为操作数据库文件而设计的 抽象计算引擎

  • 它有一个存储中间数据的 存储栈
  • 每条指令包含 一个操作码 和 不超过三个额外的操作数

B-树B-Tree

一个SQLite数据库使用 B-树 的形式存储在磁盘上,B-树的实现位于源文件 btree.c 中

  • 数据库中的 每个表 和 索引 使用一棵 单独的 B-树
  • 所有的B-树存放在 同一个磁盘文件 中
  • 文件格式的细节被记录在 btree.c开头的备注 里
  • B-树子系统的接口在头文件 btree.h 中定义

页面高速缓存Page Cache

B-树模块以固定大小的数据块形式从磁盘上请求信息,默认的块大小是 1024 个字节,但是可以在512和65536个字节之间变化

  • 页面高速缓存负责 读 、 写 和 缓存 这些数据块
  • 页面高速缓存还提供 回滚 和 原子提交 的抽象,并且管理数据文件的 锁定
  • B-树驱动模块从页面高速缓存中请求特定的页
  • 当它想修改页面、想提交或回滚当前修改时,它也会通知页面高速缓存

    页面高速缓存处理所有麻烦的细节,以确保请求能够快速、安全而有效地被处理
    

页面高速缓存的代码实现被包含在单一的C源文件 pager.c 中。页面高速缓存子系统的接口在头文件 pager.h 中定义

OS接口

为了在POSIX和Win32操作系统之间提供移植性,SQLite使用一个 抽象层 来提供操作系统接口

  • OS抽象层的接口在 os.h 中定义
  • 每种支持的操作系统有各自的实现:
    • Unix使用os_unix.c
    • Windows使用os_win.c,等等
    • 每个特定操作系统的实现通常都有自己的头文件,如os_unix.h, os_win.h等

实用工具 Utilities

  • 内存分配和字符串比较函数位于 util.c 中
  • 语法分析器使用的符号表用Hash表来维护,其实现位于 hash.c 中
  • 源文件 utf.c 包含Unicode转换子程序
  • SQLite有自己的printf()实现(带一些扩展功能),在 printf.c 中
  • 还有自己的随机数生成器,在 random.c 中

测试代码

如果计算回归测试脚本,超过一半的SQLite代码将被测试

  • 主要代码文件中有许多assert()语句
  • 源文件test1.c通过test5.c和md5.c实现只用于测试目的的一些扩展
  • os_test.c后端接口用来模拟断电,以验证页面高速缓存的崩溃恢复机制

模块作用

SQLite 由以下几个主要模块组成:SQL 编译器、内核、后端。

  • 接口 :接口由SQLite C API组成,程序可以通过API与SQLite数据库进行交互
  • 编译器 :
    1. 分词器 Tokenizer 和 分析器 Parser 对执行的SQL语句进行语法检查
    2. 生成 语法树 方便 VDBE代码生成器 使用
    3. 把语法树传给 VDBE代码生成器 Code Generator 处理
    4. 代码生成器根据语法树生成 VDBE的类汇编语言操作码
  • 后端 :由 B-树 B-tree , 页缓存管理 pager 和 操作系统接口 构成。B-tree和Pager共同对数据进行管理
    • B-tree用与对数据建立索引,它维护着各个页面之间的复杂的关系,便于快速找到所需数据
    • Pager的主要作用就是通过OS接口在B-tree和硬盘之间传递页面
Next: 进程 Previous:简介 Home: SQLite 源码分析