SQLite中的B-Tree实现细节

在SQLite的实现中，一个文件可以含有1个或的过独立的BTree。每一个BTree由它的根页的索引来标识。所有入口的key和数据组成了有效

SQLite在存储在外部的数据库是以B-Tree来组织的。关于B-tree的细节，，参考
**
** Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
** "Sorting And Searching", pages 473-480. Addison-Wesley
** Publishing Company, Reading, Massachusetts.
**
基本思想是文件包含的每一页都包括N个数据库入口和N+1个指向子页的指针。文件分成很多页存储。为什么这么干，因为内存分页管理机制闹得。外存中每个页就是B树的一个节点。
----------------------------------------------------------------
| Ptr(0) | Key(0) | Ptr(1) | Key(1) | ... | Key(N-1) | Ptr(N) |
----------------------------------------------------------------
Ptr(0)指向的页上的所有的key的值都小于Key(0)。所有Ptr(1)指向的页和子页的所有的key的值都大于Key(0)，小于Key(1)。所有Ptr(N)指向的页和子页的key的值都大于Key(N-1)，等等。

为了知道一个特定的key，需要从磁盘上以O(long(M))来读取，其中M是树的阶数。内存中找不到了，就发生缺页中断。