<td align="center" colspan=2>Next</td><td align="center" colspan=1>Ksz<br>(hi)</td><td align="center" colspan=1>Dsz<br>(hi)</td><td align="center" colspan=2>Datasize<br>(low)</td><td align="center" colspan=1>Payload</td><td align="center" colspan=4>Overflow<br>Pointer</td></tr></table></blockquote><p>The first four bytes are the pointer.  The size of the key is a 24-bitwhere the upper 8 bits are taken from byte 8 and the lower 16 bits aretaken from bytes 4 and 5 (or bytes 5 and 4 on little-endian machines.)The size of the data is another 24-bit value where the upper 8 bitsare taken from byte 9 and the lower 16 bits are taken from bytes 10 and11 or 11 and 10, depending on the byte order.  Bytes 6 and 7 are theoffset to the next cell in the linked list of all cells on the currentpage.  This offset is 0 for the last cell on the page.</p><p>The payload itself can be any number of bytes between 1 and 1048576.But space to hold the payload is allocated in 4-byte chunks up to238 bytes.  If the entry contains more than 238 bytes of payload, thenadditional payload data is stored on a linked list of overflow pages.A 4 byte page number is appended to the cell that contains the firstpage of this linked list.</p><p>Each overflow page begins with a 4-byte value which is thepage number of the next overflow page in the list.   This value is0 for the last page in the list.  The remaining1020 bytes of the overflow page are available for storing payload.Note that a full page is allocated regardless of the number of overflowbytes stored.  Thus, if the total payload for an entry is 239 bytes,the first 238 are stored in the cell and the overflow page stores justone byte.</p><p>The structure of an overflow page looks like this:</p><blockquote><table border=1 cellspacing=0 cellpadding=5><tr><td align="center" width=20>0</td><td align="center" width=20>1</td><td align="center" width=20>2</td><td align="center" width=20>3</td><td align="center" width=200>4 ... 1023</td></tr><tr><td align="center" colspan=4>Next Page</td><td align="center" colspan=1>Overflow Data</td></tr></table></blockquote><p>All space on a b-tree page which is not used by the header or by cellsis filled by freeblocks.  Freeblocks, like cells, are variable in size.The size of a freeblock is at least 4 bytes and is always a multiple of4 bytes.The first 4 bytes contain a header and the remaining bytesare unused.  The structure of the freeblock is as follows:</p><blockquote><table border=1 cellspacing=0 cellpadding=5><tr><td align="center" width=20>0</td><td align="center" width=20>1</td><td align="center" width=20>2</td><td align="center" width=20>3</td><td align="center" width=200>4 ... 1015</td></tr><tr><td align="center" colspan=2>Size</td><td align="center" colspan=2>Next</td><td align="center" colspan=1>Unused</td></tr></table></blockquote><p>Freeblocks are stored in a linked list in increasing order.  That isto say, the first freeblock occurs at a lower index into the page thanthe second free block, and so forth.  The first 2 bytes of the headerare an integer which is the total number of bytes in the freeblock.The second 2 bytes are the index into the page of the next freeblockin the list.  The last freeblock has a Next value of 0.</p><p>When a new b-tree is created in a database, the root page of the b-treeconsist of a header and a single 1016 byte freeblock.  As entries areadded, space is carved off of that freeblock and used to make cells.When b-tree entries are deleted, the space used by their cells is convertedinto freeblocks.  Adjacent freeblocks are merged, but the page can stillbecome fragmented.  The b-tree code will occasionally try to defragmentthe page by moving all cells to the beginning and constructing a singlefreeblock at the end to take up all remaining space.</p><h4>3.3 &nbsp; The B-Tree Free Page List</h4><p>When information is removed from an SQLite database such that one ormore pages are no longer needed, those pages are added to a list offree pages so that they can be reused later when new information isadded.  This subsection describes the structure of this freelist.</p><p>The 32-bit integer beginning at byte-offset 52 in page 1 of the databasecontains the address of the first page in a linked list of free pages.If there are no free pages available, this integer has a value of 0.The 32-bit integer at byte-offset 56 in page 1 contains the number offree pages on the freelist.</p><p>The freelist contains a trunk and many branches.  The trunk ofthe freelist is composed of overflow pages.  That is to say, each pagecontains a single 32-bit integer at byte offset 0 whichis the page number of the next page on the freelist trunk.The payload areaof each trunk page is used to record pointers to branch pages. The first 32-bit integer in the payload area of a trunk pageis the number of branch pages to follow (between 0 and 254)and each subsequent 32-bit integer is a page number for a branch page.The following diagram shows the structure of a trunk freelist page:</p><blockquote><table border=1 cellspacing=0 cellpadding=5><tr><td align="center" width=20>0</td><td align="center" width=20>1</td><td align="center" width=20>2</td><td align="center" width=20>3</td><td align="center" width=20>4</td><td align="center" width=20>5</td><td align="center" width=20>6</td><td align="center" width=20>7</td><td align="center" width=200>8 ... 1023</td></tr><tr><td align="center" colspan=4>Next trunk page</td><td align="center" colspan=4># of branch pages</td><td align="center" colspan=1>Page numbers for branch pages</td></tr></table></blockquote><p>It is important to note that only the pages on the trunk of the freelistcontain pointers to other pages.  The branch pages contain nodata whatsoever.  The fact that the branch pages are completelyblank allows for an important optimization in the paging layer.  Whena branch page is removed from the freelist to be reused, it is notnecessary to write the original content of that page into the rollbackjournal.  The branch page contained no data to begin with, so there isno need to restore the page in the event of a rollback.  Similarly,when a page is not longer needed and is added to the freelist as a branchpage, it is not necessary to write the content of that pageinto the database file.Again, the page contains no real data so it is not necessary to record thecontent of that page.  By reducing the amount of disk I/O required,these two optimizations allow some database operationsto go four to six times faster than they would otherwise.</p><h3>4.0 &nbsp; The Schema Layer</h3><p>The schema layer implements an SQL database on top of one or moreb-trees and keeps track of the root page numbers for all b-trees.Where the b-tree layer provides only unformatted data storage witha unique key, the schema layer allows each entry to contain multiplecolumns.  The schema layer also allows indices and non-unique key values.</p><p>The schema layer implements two separate data storage abstractions:tables and indices.  Each table and each index uses its own b-treebut they use the b-tree capabilities in different ways.  For a table,the b-tree key is a unique 4-byte integer and the b-tree data is thecontent of the table row, encoded so that columns can be separatelyextracted.  For indices, the b-tree key varies in size depending on thesize of the fields being indexed and the b-tree data is empty.</p><h4>4.1 &nbsp; SQL Table Implementation Details</h4><p>Each row of an SQL table is stored in a single b-tree entry.The b-tree key is a 4-byte big-endian integer that is the ROWIDor INTEGER PRIMARY KEY for that table row.The key is stored in a big-endian format sothat keys will sort in numerical order using memcmp() function.</p><p>The content of a table row is stored in the data portion ofthe corresponding b-tree table.  The content is encoded to allowindividual columns of the row to be extracted as necessary.  Assumingthat the table has N columns, the content is encoded as N+1 offsetsfollowed by N column values, as follows:</p><blockquote><table border=1 cellspacing=0 cellpadding=5><tr><td>offset 0</td><td>offset 1</td><td><b>...</b></td><td>offset N-1</td><td>offset N</td><td>value 0</td><td>value 1</td><td><b>...</b></td><td>value N-1</td></tr></table></blockquote><p>The offsets can be either 8-bit, 16-bit, or 24-bit integers dependingon how much data is to be stored.  If the total size of the contentis less than 256 bytes then 8-bit offsets are used.  If the total sizeof the b-tree data is less than 65536 then 16-bit offsets are used.24-bit offsets are used otherwise.  Offsets are always little-endian,which means that the least significant byte occurs first.</p><p>Data is stored as a nul-terminated string.  Any empty string consistsof just the nul terminator.  A NULL value is an empty string with nonul-terminator.  Thus a NULL value occupies zero bytes and an empty stringoccupies 1 byte.</p><p>Column values are stored in the order that they appear in the CREATE TABLEstatement.  The offsets at the beginning of the record contain thebyte index of the corresponding column value.  Thus, Offset 0 containsthe byte index for Value 0, Offset 1 contains the byte offsetof Value 1, and so forth.  The number of bytes in a column value canalways be found by subtracting offsets.  This allows NULLs to berecovered from the record unambiguously.</p><p>Most columns are stored in the b-tree data as described above.The one exception is column that has type INTEGER PRIMARY KEY.INTEGER PRIMARY KEY columns correspond to the 4-byte b-tree key.When an SQL statement attempts to read the INTEGER PRIMARY KEY,the 4-byte b-tree key is read rather than information out of theb-tree data.  But there is still an Offset associated with theINTEGER PRIMARY KEY, just like any other column.  But the Valueassociated with that offset is always NULL.</p><h4>4.2 &nbsp; SQL Index Implementation Details</h4><p>SQL indices are implement using a b-tree in which the key is usedbut the data is always empty.  The purpose of an index is to mapone or more column values into the ROWID for the table entry thatcontains those column values.</p><p>Each b-tree in an index consists of one or more column values followedby a 4-byte ROWID.  Each column value is nul-terminated (even NULL values)and begins with a single character that indicates the datatype for thatcolumn value.  Only three datatypes are supported: NULL, Number, andText.  NULL values are encoded as the character 'a' followed by thenul terminator.  Numbers are encoded as the character 'b' followed bya string that has been crafted so that sorting the string using memcmp()will sort the corresponding numbers in numerical order.  (See thesqliteRealToSortable() function in util.c of the SQLite sources foradditional information on this encoding.)  Numbers are also nul-terminated.Text values consists of the character 'c' followed by a copy of thetext string and a nul-terminator.  These encoding rules result inNULLs being sorted first, followed by numerical values in numericalorder, followed by text values in lexicographical order.</p><h4>4.4 &nbsp; SQL Schema Storage And Root B-Tree Page Numbers</h4><p>The database schema is stored in the database in a special tabled named"sqlite_master" and which always has a root b-tree page number of 2.This table contains the original CREATE TABLE,CREATE INDEX, CREATE VIEW, and CREATE TRIGGER statements used to definethe database to begin with.  Whenever an SQLite database is opened,the sqlite_master table is scanned from beginning to end and all the original CREATE statements are played back through the parserin order to reconstruct an in-memory representation of the databaseschema for use in subsequent command parsing.  For each CREATE TABLEand CREATE INDEX statement, the root page number for the correspondingb-tree is also recorded in the sqlite_master table so that SQLite willknow where to look for the appropriate b-tree.</p><p>SQLite users can query the sqlite_master table just like any other tablein the database.  But the sqlite_master table cannot be directly written.The sqlite_master table is automatically updated in response to CREATEand DROP statements but it cannot be changed using INSERT, UPDATE, orDELETE statements as that would risk corrupting the database.</p><p>SQLite stores temporary tables and indices in a separatefile from the main database file.  The temporary table database fileis the same structure as the main database file.  The schema tablefor the temporary tables is stored on page 2 just as in the maindatabase.  But the schema table for the temporary database named"sqlite_temp_master" instead of "sqlite_master".  Other than thename change, it works exactly the same.</p><h4>4.4 &nbsp; Schema Version Numbering And Other Meta-Information</h4><p>The nine 32-bit integers that are stored beginning at byte offset60 of Page 1 in the b-tree layer are passed up into the schema layerand used for versioning and configuration information.  The meaningof the first four integers is shown below.  The other five are currentlyunused.</p><ol><li>The schema version number</li><li>The format version number</li><li>The recommended pager cache size</li><li>The safety level</li></ol><p>The first meta-value, the schema version number, is used to detect whenthe schema of the database is changed by a CREATE or DROP statement.Recall that when a database is first opened the sqlite_master table isscanned and an internal representation of the tables, indices, views,and triggers for the database is built in memory.  This internalrepresentation is used for all subsequent SQL command parsing andexecution.  But what if another process were to change the schemaby adding or removing a table, index, view, or trigger?  If the originalprocess were to continue using the old schema, it could potentiallycorrupt the database by writing to a table that no longer exists.To avoid this problem, the schema version number is changed whenevera CREATE or DROP statement is executed.  Before each command isexecuted, the current schema version number for the database fileis compared against the schema version number from when the sqlite_mastertable was last read.  If those numbers are different, the internalschema representation is erased and the sqlite_master table is rereadto reconstruct the internal schema representation.(Calls to sqlite_exec() generally return SQLITE_SCHEMA when this happens.)</p><p>The second meta-value is the schema format version number.  Thisnumber tells what version of the schema layer should be used tointerpret the file.  There have been changes to the schema layerover time and this number is used to detect when an older databasefile is being processed by a newer version of the library.As of this writing (SQLite version 2.7.0) the current format versionis "4".</p><p>The third meta-value is the recommended pager cache size as set by the DEFAULT_CACHE_SIZE pragma.  If the value is positive itmeans that synchronous behavior is enable (via the DEFAULT_SYNCHRONOUSpragma) and if negative it means that synchronous behavior isdisabled.</p><p>The fourth meta-value is safety level added in version 2.8.0.A value of 1 corresponds to a SYNCHRONOUS setting of OFF.  In otherwords, SQLite does not pause to wait for journal data to reach the disksurface before overwriting pages of the database.  A value of 2 correspondsto a SYNCHRONOUS setting of NORMAL.  A value of 3 corresponds to aSYNCHRONOUS setting of FULL. If the value is 0, that means it has notbeen initialized so the default synchronous setting of NORMAL is used.</p>}footer $rcsid