On 8/11/17, Scott Robison <sc...@casaderobison.com> wrote:
> My understanding is that SQLite doesn't use the traditional definition of
> b-tree because it doesn't use fixed size records/keys. It will cram as few
> or as many as possible.
More records crammed into one page means that fewer pages need to be
read, which makes things run faster. It also means that less disk
space gets used.
The in-tree portion of each record is size limited to ensure that at
least four records fit on each page. Otherwise, the btree might
degenerate into a linked list. The tail of records that exceed the
maximum in-tree record size is written onto overflow pages.
For ordinary rowid tables, a traditional b-tree is used, which means
that only the key is stored on intermediate pages and all the content
appears in the leaves. Since the keys are always just a rowid and
typically take only a few bytes, there are ordinarily a large number
keys per page. You can run the sqlite3_analyzer.exe utility program
(available in the "sqlite-tools-*" bundles on the
https://sqlite.org/download.html page) to see the average number of
keys/page for each table and index. Or you can use the DBSTAT virtual
table (https://www.sqlite.org/dbstat.html) to query for that
information on a page-by-page basis.
For indexes and WITHOUT ROWID tables, the keys can be much larger, and
so the minimum-four-per-page rule is more likely to come into play.
D. Richard Hipp
sqlite-users mailing list