Documentation Source Text

Check-in [ea334221a0]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Correction to how Knuth names B-Tree algorithm variants in the file format document.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: ea334221a05405039815ce2e250a6b567da40ca03afeb5c7a503f95ced368cce
User & Date: drh 2020-06-28 16:36:32.368
Context
2020-06-29
11:40
Merge fixes from the 3.32 branch. (check-in: e3d95c44b7 user: drh tags: trunk)
2020-06-28
16:36
Correction to how Knuth names B-Tree algorithm variants in the file format document. (check-in: ea334221a0 user: drh tags: trunk)
2020-06-19
13:05
Create a new documentation page devoted to describing the use and purpose of the sqlite_schema table. Work-in-progress. (check-in: 29b01bac87 user: drh tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to pages/fileformat2.in.
︙︙
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482

<tcl>hd_fragment btree {B*-Trees} {B-tree}</tcl>
<h2>B-tree Pages</h2>

<p>The b-tree algorithm provides key/data storage with unique and
ordered keys on page-oriented storage devices.
For background information on b-trees, see
Knuth, <u>The Art Of Computer Programming</u>, Volume 3 "Sorting
and Searching", pages 471-479.  Two kinds of b-trees are used by
SQLite.  The algorithm that Knuth calls "B*-Tree" stores all data
in the leaves of the tree.  SQLite calls this variety of b-tree
a "table b-tree". The algorithm that Knuth calls simply "B-Tree"
stores both the key and the data together in both leaves
and in interior pages.  In the SQLite implementation, the original
B-Tree algorithm stores keys only, omitting the data entirely, and
is called an "index b-tree".

<p>A b-tree page is either an interior page or a leaf page.
A leaf page contains keys and in the case of a table b-tree each
key has associated data.  An interior page contains
K keys together with K+1 pointers to child b-tree pages.
A "pointer" in an interior b-tree page is just the 31-bit integer
page number of the child page.</p>








|
|
|
<
<
<
<
|








461
462
463
464
465
466
467
468
469
470




471
472
473
474
475
476
477
478

<tcl>hd_fragment btree {B*-Trees} {B-tree}</tcl>
<h2>B-tree Pages</h2>

<p>The b-tree algorithm provides key/data storage with unique and
ordered keys on page-oriented storage devices.
For background information on b-trees, see
Knuth, <u>The Art Of Computer Programming</u>, Volume 3 "Sorting
and Searching", pages 471-479.  Two variants of b-trees are used by
SQLite.  "Table b-trees" use a 64-bit signed integer key and store
all data in the leaves.  "Index b-trees" use arbitrary keys and store no




data at all.

<p>A b-tree page is either an interior page or a leaf page.
A leaf page contains keys and in the case of a table b-tree each
key has associated data.  An interior page contains
K keys together with K+1 pointers to child b-tree pages.
A "pointer" in an interior b-tree page is just the 31-bit integer
page number of the child page.</p>
︙︙