欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  数据库

SQLite中的B-Tree实现细节

程序员文章站 2022-04-26 13:24:46
...

在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是树的阶数。内存中找不到了,就发生缺页中断。