Documentation Source Text

that consists of a single page that is both a leaf and the root.
Because there are pointers from parents to children, every page of a
complete b-tree can be located if only the root page is known.  Hence,
b-trees are identified by their root page number.</p>

<p>A b-tree page is either a table b-tree page or an index b-tree page.
All pages within each complete b-tree are of the same type: either table
or index.  There is a one table b-trees in the database file
for each rowid table in the database schema, including system tables
such as sqlite_master.  There is one index b-trees
in the database file for each index in the schema, including implied indexes
created by uniqueness constraints.  There are no b-trees associated with
[virtual tables].  Specific virtual table implementations might make use
of [shadow tables] for storage, but those shadow tables will have separate
entries in the database schema.  [WITHOUT ROWID] tables use index b-trees
rather than a table b-trees, so there is one
index b-tree in the database file for each [WITHOUT ROWID] table.

<tcl>hd_fragment varint {variable-length integer} {varint}</tcl>

<p>A variable-length integer or "varint" is a static Huffman encoding
of 64-bit twos-complement integers that uses less space for small positive 
values. 
A varint is between 1 and 9 bytes in length.  The varint consists of either
zero or more byte which have the high-order bit set followed by a single byte
with the high-order bit clear, or nine bytes, whichever is shorter.
The lower seven bits of each of the first eight bytes and all 8 bits of
the ninth byte are used to reconstruct the 64-bit twos-complement integer.
Varints are big-endian: bits taken from the earlier byte of the varint
are the more significant than bits taken from the later bytes. </p>

<p>The format of a cell depends on which kind of b-tree page the cell

pages.
<li>A 4-byte big-endian integer page number for the first page of the
overflow page list - omitted if all payload fits on the b-tree page.
</ul></p></dd>

<dt><p>Index B-Tree Interior Cell (header 0x02):</p></dt>
<dd><p><ul>
<li>A 4-byte big-endianpage number which is the left child pointer.
<li>A varint which is the total number of bytes of key payload, including any
overflow
<li>The initial portion of the payload that does not spill to overflow
pages.
<li>A 4-byte big-endian integer page number for the first page of the
overflow page list - omitted if all payload fits on the b-tree page.
</ul></p></dd>

<blockquote><dl>
<dt>Table B-Tree Leaf Cell:</dt>
<dd><p>
^If the payload size P is less than or equal to U-35 then
the entire payload is stored on the b-tree leaf page.  
^(Let M be ((U-12)*32/255)-23.  If P is greater than U-35
then the number of byte stored on the b-tree leaf page is the smaller of
M+((P-M)%(U-4)) and U-35.)^
^(Note that number of bytes stored on the leaf page is never less than M.)^
</p></dd>

<dt>Table B-Tree Interior Cell:</dt>
<dd><p>
Interior pages of table b-trees have no payload and so there is never
any payload to spill.
</p></dd>

<dt>Index B-Tree Leaf Or Interior Cell:</dt>
<dd><p>
^(Let X be ((U-12)*64/255)-23).  If the payload size P is less than
or equal to X then the entire payload is stored on the b-tree page.)^
^(Let M be ((U-12)*32/255)-23.  If P is greater than X then the number
of byte stored on the b-tree page is the smaller of
M+((P-M)%(U-4)) and X.)^
^(Note that number of bytes stored on the index page is never less than M.)^
</p></dd>
</dl></blockquote>

<p>The overflow thresholds are designed to give a minimum fanout of
4 for index b-trees and to make sure enough of the payload

<p>^(In a database that uses ptrmap pages, all pages at locations identified
by the computation in the previous paragraph must be ptrmap page and no
other page may be a ptrmap page.  Except, if the byte-lock page happens to
fall on the same page number as a ptrmap page, then the ptrmap is moved
to the following page for that one case.)^</p>

<p>Each 5-byte entry on a ptrmap page provides back-link information about 
one of pages that immediately follow the pointer map.  ^(If page B is a
ptrmap page then back-link information about page B+1 is provided by
the first entry on the pointer map.  Information about page B+2 is
provided by the second entry.  And so forth.)^</p>

<p>Each 5-byte ptrmap entry consists of one byte of "page type" information
followed by a 4-byte big-endian page number.  Five page types are recognized:
</p>

integer key for each entry in the table b-tree.</p>

<p> ^The content of each SQL table row is stored in the database file by
first combining the values in the various columns into a byte array
in the record format, then storing that byte array as the payload in
an entry in the table b-tree.  ^The order of values in the record is
the same as the order of columns in the SQL table definition.
^When an SQL table that includes an
[INTEGER PRIMARY KEY] column (which aliases the [rowid]) then that
column appears in the record as a NULL value.  ^SQLite will always use
the table b-tree key rather than the NULL value when referencing the
[INTEGER PRIMARY KEY] column.</p>

<p> ^If the [affinity] of a column is REAL and that column contains a
value that can be converted to an integer without loss of information

and virtual tables, the rootpage column is 0 or NULL.</p>

<p>^(The sqlite_master.sql column stores SQL text that describes the
object.  This SQL text is a [CREATE TABLE], [CREATE VIRTUAL TABLE],
[CREATE INDEX],
[CREATE VIEW], or [CREATE TRIGGER] statement that if evaluated against
the database file when it is the main database of a [database connection]
would recreated the object.)^  The text is usually a copy of the original
statement used to create the object but with normalizations applied so
that the text conforms to the following rules:

<ul>
<li>^The CREATE, TABLE, VIEW, TRIGGER, and INDEX keywords at the beginning
of the statement are converted to all upper case letters.
<li>^The TEMP or TEMPORARY keyword is removed if it occurs after the 

<ul>
<li><p>Indices with names of the form "sqlite_autoindex_TABLE_N" that
       are used to implement [UNIQUE] and [PRIMARY KEY] constraints on
       ordinary tables.

<li><p>A table with the name "sqlite_sequence" that is used to keep track
       of the maximum historical [INTEGER PRIMARY KEY] for a table that
       using [AUTOINCREMENT].

<li><p>Tables with names of the form "sqlite_statN" where N is an integer.
       Such tables store database statistics gathered by the [ANALYZE]
       command and used by the query planner to help determine the best
       algorithm to use for each query.
</ul>

that contain between 10 and 40 samples that are distributed across
the key space and with large nEq values.

<p>^(In a well-formed sqlite_stat3 table, the samples for any single
index must appear in the same order that they occur in the index.  
In other words, if the entry with left-most column S1 is earlier in
the index b-tree than the
entry with lef-most column S2, then in the sqlite_stat3 table, 
sample S1 must have a smaller rowid than sample S2.)^

<tcl>hd_fragment stat4tab {sqlite_stat4} SQLITE_STAT4</tcl>
<h4>2.6.6 The sqlite_stat4 table</h4>

<p>The sqlite_stat4 is only created and is only used if SQLite is compiled
with [SQLITE_ENABLE_STAT4] and if the SQLite version number is

    <td>^(The sqlite_stat4.nLt column holds a list of N integers where
    the K-th integer is the approximate number of entries in the
    index whose K left-most columns are collectively less than the 
    K left-most columns of the sample.)^

<tr><td valign="top" align="right">nDLt:</td>
    <td>^(The sqlite_stat4.nDLt column holds a list of N integers where
    the K-th integers is the approximate
    number of entries in the index that are distinct in the first K columns and
    that are whose left-most K columns are collectively less than the left-most
    K columns of the sample.)^
</table>
</center>

<p>The sqlite_stat4 is a generalization of the sqlite_stat3 table.  The
sqlite_stat3 table provides information about the left-most column of an
index whereas the sqlite_stat4 table provides information about all columns