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 | SQL archive |
| Timelines: | family | ancestors | descendants | both | trunk |
| Files: | files | file ages | folders |
| SHA3-256: |
ea334221a05405039815ce2e250a6b56 |
| User & Date: | drh 2020-06-28 16:36:32 |
Context
|
2020-06-29
| ||
| 11:40 | Merge fixes from the 3.32 branch. (Leaf 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
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>
|