Documentation Source Text

<title>SQLite B-Tree Module</title>
<tcl>

hd_keywords {btree design}
source [file join $::DOC pages fancyformat.tcl]
fancyformat_document "SQLite B-Tree Module" hlr50000.txt {

  [h1 "Document Overview"]

  [h2 "Scope and Purpose"]

  <ul>
    <li><p> To make it easier to maintain, test and improve this critical
            sub-system of the SQLite software library.

    <li><p> To facilitate development of compatible backend modules that can 
            be used with other SQLite sub-systems, either for experimental or 
            production purposes.
  </ul>

  <p>
    It is important to note that, even given the second bullet point above,
    the interfaces and sub-systems described in this document are not stable.
    They may be changed in any way with each new SQLite release. Any 
    external software development that uses these interfaces must be prepared
    to adapt to interface refactoring without notice.

  [h2 "Document and Requirements Organization"]

  [h2 "Glossary"]

  [h1 "Module Requirements"]

  <p>
    The SQLite B-Tree module, the software module described by this document,
    is designed to query and modify a database stored using the database image
    format described in <cite>ref_file_format</cite>. Database images may
    exist only in volatile main-memory (in-memory databases), or may be stored 
    persistently within the file-system. Or, a database image may be stored
    primarily in main-memory with the file-system used as secondary storage if
    the database image grows too large.

  <p><i>
    One-to-many connections to each database. Need a term for an in-memory cache (struct BtShared).
  </i>

  <p><i>
    Roughly what is encapsulated by the module.
  </i>

    [h2 "Functional Requirements"]

    <p>
      This section contains requirements describing the functionality required 
      from the B-Tree module.

    [h3 "Opening and Closing Connections"]

  <ul>
    <li> Open connection.
    <li> Close connection.
  </ul>

      [fancyformat_import_requirement H50010]

    [h3 "New Database Image Configuration"]
  <ul>
    <li> Set/get page-size.
    <li> Set/get auto-vacuum capable.
  </ul>

    [h3 "Transaction and Savepoint Functions"]
  <ul>
    <li> Begin transaction.
    <li> CommitPhaseOne()/CommitPhaseTwo().
    <li> Rollback transaction.
    <li> Query for transaction state (no-transaction, readonly, read-write).
    <li> Begin savepoint(s).
    <li> Release savepoint(s).
    <li> Rollback savepoint(s).
  </ul>

    [h3 "Reading From the Database Image"]
  <ul>
    <li> Open b-tree cursor.
    <li> Close b-tree cursor.
    <li> Seek cursor (and all of its variants).
    <li> Retrieve current key/data pointed to by cursor.
    <li> Read selected database header fields.
  </ul>

    [h3 "Writing to the Database Image"]
  <ul>
    <li> Create new b-tree structure.
    <li> Drop existing b-tree structure.
    <li> Clear b-tree structure contents.
    <li> Incremental vacuum step.
    <li> Write selected database header fields.
    <li> Delete entry pointed to by cursor.
    <li> Insert new entry into b-tree.
  </ul>

    [h3 "Backup API Requirements"]
  <ul>
    <li> Callbacks for backup module.
    <li> Page read/write APIs for backup module.
  </ul>

    [h3 "Configuration Requirements"]

  <ul>
    <li> Set codec function (encryption).
    <li> Set/get the current locking_mode (exclusive or normal).
    <li> Set/get the current journal_mode (delete, persist, off, truncate or memory).
    <li> Set/get the current journal file size-limit.
    <li> Set/get the current database file size-limit (MaxPageCount()).
    <li> Set/get the current cache-size.
    <li> Set/get the current safety-level.
    <li> Query for the database file name.
    <li> Query for the journal file name.
    <li> <span class=todo>Where does the busy-handler come in?</span>
  </ul>

    [h3 "Multi-User Database Requirements"]
  <ul>
    <li> Mutexes/thread-safety features.
    <li> Lock on schema memory object.
    <li> Locks on b-tree tables.
    <li> "Unlock notify" feature.
  </ul>

  [h2 "Other Requirements"]

    [h3 "Caching and Memory Management Requirements"]
  <ul>
    <li> Memory allocation related features (pcache, scratch memory, other...).
    <li> Default pcache implementation (sqlite3_release_memory()).
    <li> Schema memory object allocation (destructor registration).
  </ul>

    [h3 "Fault Tolerance Requirements"]
  <ul>
    <li> Don't corrupt the database. Various modes and the expectations of them.
  </ul>



  [h1 "Module API"]

      <p class=todo>
        Description of the interface in btree.h. Also other interfaces accessed by
        external modules. Including release_memory() and those pager interfaces that
        are accessed directly by other modules. All of these requirements will be
        descended/derived from requirements in the previous sections. Some of the
        text could/should be pulled in from btree.h.

      <p class=todo>
	  The name of sqlite3BtreeBeginStmt() should probably change to
	  sqlite3BtreeOpenSavepoint(). Matches the pager layer and is a more
	  accurate description of the function.

      <p class=todo>
        There are only a few places in which the pager object is used directly,
        always to call some trivial get/set configuration function. These should
	  be replaced somehow with sqlite3BtreeXXX() APIs. Also, the current
	  approach is probably Ok, but worth looking it over for thread-safety
        issues.

      <p class=todo>
	  It would be easier to write up if the dependency between the B-Tree
        layer and the sqlite3 structure did not exist. At present, it is used for:
        
          <br> * The unlock-notify feature (arguments to sqlite3ConnectionBlocked() are database handles),
          <br> * Accessing the SQLITE_ReadUncommitted flag,
          <br> * Invoking the busy-handler callback,
          <br> * During sqlite3BtreeOpen(), to find the VFS to use,
          <br> * Accessing the SQLITE_SharedCache flag (for setting it),
          <br> * To check the same B-Tree is not attached more than once in shared-cache mode,
          <br> * To link the B-Tree into the pointer-order list of shared-cache b-trees used by the same handle (used for mutexes).
          <br> * To determine if an in-memory sub-journal should be used.
          <br> * To know how many savepoints are open in BtreeBeginTrans().
          <br> * Many, many times to assert() that the db mutex is held when the b-tree layer is accessed..

  [h1 "Module Implementation"]

  [h2 "Database Image Traversal and Manipulation"]

     <p class=todo>
       This section should describe exactly how bits and bytes are shifted
       around when the database image is traversed and modified. i.e. how
       a cursor seek is implemented, how the b-tree balancing works, deleting
       an internal cell from an index b-tree etc.

  [h2 "Transactions and Savepoints"]

     <p class=todo>
       Requirements surrounding how transactions are made atomic and isolated.
       Also how savepoints are implemented. What happens to active cursors after
       a rollback or savepoint-rollback.

  [h1 References]

  <table id="refs" style="width:auto; margin: 1em 5ex">
    [Ref 1 ref_file_format {
      SQLite Online Documentation,<u>SQLite Database File Format</u>,
      <a href="fileformat.html">http://www.sqlite.org/fileformat.html</a>.
    }]
    [Ref 2 ref_pcache_interface {
      SQLite Online Documentation,<u>Application Defined Page Cache</u>,
      <a href="c3ref/pcache_methods.html">http://www.sqlite.org/c3ref/pcache_methods.html</a>.
    }]
    [Ref 3 ref_os_interface {
      SQLite Online Documentation,<u>OS Interface Object</u>,
      <a href="c3ref/vfs.html">http://www.sqlite.org/c3ref/vfs.html</a>.
    }]

  </table>
}

</tcl>

catch { array unset ::SectionNumbers }
set ::SectionNumbers(1) 0
set ::SectionNumbers(2) 0
set ::SectionNumbers(3) 0
set ::SectionNumbers(fig) 0
catch { set TOC "" }
catch { array unset ::References }

proc H {iLevel zTitle {zName ""}} {

  set zNumber ""
  for {set i 1} {$i <= 4} {incr i} {
    if {$i < $iLevel} {
      append zNumber "$::SectionNumbers($i)."
    }
    if {$i == $iLevel} {
      append zNumber "[incr ::SectionNumbers($i)]."
    }
    if {$i > $iLevel} {
      set ::SectionNumbers($i) 0
    }
  }
  # set zNumber [string range $zNumber 0 end-1]

  if {$zName == ""} {
    set zName [string range "section_[string map {. _} $zNumber]" 0 end-1]
  } else {
    set ::References($zName) [list $zNumber $zTitle]
  }

  append ::TOC [subst {
    <div style="margin-left:[expr $iLevel*6]ex">
    <a href="#$zName">${zNumber} $zTitle</a>
    </a></div>
  }]

  return "<h$iLevel id=\"$zName\">$zNumber $zTitle</h$iLevel>\n"
}
proc h1 {args} {uplevel H 1 $args}
proc h2 {args} {uplevel H 2 $args}
proc h3 {args} {uplevel H 3 $args}
proc h4 {args} {uplevel H 4 $args}

proc Figure {zImage zName zCaption} {
  incr ::SectionNumbers(fig)
  set ::References($zName) [list $::SectionNumbers(fig) $zCaption]
  subst {
      <center>
      <a name="$zName"></a>
      <img src="images/fileformat/$zImage">
      <p><i>Figure $::SectionNumbers(fig) - $zCaption</i>
      </center>
  }
}

proc sort_by_length {lhs rhs} {
  return [expr [string length $lhs] - [string length $rhs]]
}

set ::Random 0
proc randomstring {} {
  incr ::Random
  return [expr $::Random + rand()]
}

proc Ref {no id details} {
  set ::References($id) "\[$no\]"
  return "<tr><td style=\"width:5ex ; vertical-align:top\" id=\"$id\">\[$no\]<td>$details"
}

proc FixReferences {body} {
  if {[info commands hd_resolve_2ndpass] ne ""} return 

  set l [list]
  foreach E [lsort -decr -index 1 -command sort_by_length $::Glossary] {
    # puts $E
    foreach {term anchor} $E {}
    set re [string map {" " [-[:space:]]+} $term]
    set re "${re}s?"

    while { [regexp -nocase $re $body thisterm] } {
      set xxx [randomstring]
      set body [regsub -nocase $re $body $xxx]
      lappend l $xxx "<a class=defnlink href=\"#$anchor\">$thisterm</a>"
    }

    # set body [regsub -all -nocase $re $body "<a class=defnlink href=\"#$anchor\">\\0</a>"]
    # set body [regsub -all -nocase {(defnlink[^<]*) } $body "\\1&20;"]
  }

  foreach R $::Requirements {
    set body [regsub -all "(\[^=\])$R" $body "\\1<a class=reqlink href=#$R>$R</a>"]
  }

  foreach {key value} [array get ::References] {
    foreach {zNumber zTitle} $value {}
    lappend l <cite>$key</cite> "<cite><a href=\"#$key\" title=\"$zTitle\">$zNumber</a></cite>"
  }

  set body [string map $l $body]
}

set ::Glossary {}
proc Glossary {term definition} {
  set anchor [string map {" " _ ' _} $term]
  set anchor "glossary_$anchor"
  lappend ::Glossary [list $term $anchor]
  return "<tr><td class=defn><a name=\"$anchor\"></a>$term <td>$definition"
}

# Procs to generate <table> and <tr> tags. They also give alternating rows
# of the table a grey background, which can make it easier to read.
# 
proc Table {} {
  set ::Stripe 1
  return "<table class=striped>"
}
proc Tr {} {
  set ::Stripe [expr {($::Stripe+1)%2}]
  if {$::Stripe} {
    return "<tr style=\"background-color:#DDDDDD\">"
  } else {
    return "<tr>"
  }
}
proc fancyformat_import_requirement {reqid} {
  lappend ::Requirements $reqid
  return "<p class=req id=$reqid>[lindex $::ffreq($reqid) 1]</p>"
}

set ::Requirements [list]

proc fancyformat_document {zTitle lReqfile zBody} {
  unset -nocomplain ::ffreq
  foreach f $lReqfile {
    hd_read_requirement_file $::DOC/req/$f ::ffreq
  }
  set body [subst -novariables $zBody]
  hd_puts [subst {
    <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
    <html>
    <head>
    <link type="text/css" rel="stylesheet" href="images/fileformat/rtdocs.css">
    </head>
    <body>

    <div id=document_title>$zTitle</div>
    <div id=toc_header>Table Of Contents</div>

    <div id=toc>
      $::TOC
    </div id>
    [FixReferences $body]
  }]
}

<title>SQLite Database File Format</title>


<tcl>




hd_keywords {file format}


















source [file join $::DOC pages fancyformat.tcl]







fancyformat_document "SQLite Database File Format" hlr30000.txt {


















































































































[h1 "Document Overview"]

  [h2 "Scope and Purpose"]

  <p>
    

h1 "SQLite Database Files" sqlite_database_files
 
  <p>
    The bulk of this document, section <cite>database_file_format</cite>,
    contains the definition of a <i>well-formed SQLite database file</i>.
    SQLite is required to create database files that meet this definition.

          [fancyformat_import_requirement H30010]

  <p>
    Additionally, the database file should contain a serialized version
    of the logical database produced by the transaction. For all but the
    most trivial logical databases, there are many possible serial 
    representations.

          [fancyformat_import_requirement H30020]
-->

<!--
  <p>
    Section <cite>database_file_manipulation</cite> contains requirements
    describing in more detail the way in which SQLite manipulates the
    fields and data structures described in section

      <pre>
          0x53 0x51 0x4c 0x69 0x74 0x65 0x20 0x66 0x6f 0x72 0x6d 0x61 0x74 0x20 0x33 0x00</pre>

      <p>
        Interpreted as UTF-8 encoded text, this byte sequence corresponds 
        to the string "SQLite format 3" followed by a nul-terminator byte.

          [fancyformat_import_requirement H30030]

      <p>
        The 1, 2 and 4 byte unsigned integers that make up the rest of the
        database header are described in the following table.

      [Table]
        [Tr]<th>Byte Range <th>Byte Size <th width=100%>Description <th>Reqs

	     content when using overflow pages (single byte field, byte offset 23),
	     is always set to 0x20.
      </ul>

      <p>
        The following requirement encompasses all of the above.

          [fancyformat_import_requirement H30040]

      <p>
        Section <cite>database_file_format</cite> identifies six persistent
        user-visible properties of an SQLite database. The following 
        requirements describe the way in which these properties are stored.

          [fancyformat_import_requirement H30190]
          [fancyformat_import_requirement H30191]
          [fancyformat_import_requirement H30150]
          [fancyformat_import_requirement H30140]
          [fancyformat_import_requirement H30141]
          [fancyformat_import_requirement H30160]
          [fancyformat_import_requirement H30170]
          [fancyformat_import_requirement H30171]
          [fancyformat_import_requirement H30130]

      <p>
        The following requirement describes the valid range of values for the
        schema layer file format field.

          [fancyformat_import_requirement H30120]

      <p class=todo>
        See the note to do with the schema file format version above. Turns
        out this field may also be set to 0 by SQLite.

    [h3 "Pages and Page Types" "pages_and_page_types"]
      <p>

            permanently designated "pointer-map" pages. See section 
            <cite>pointer_map_pages</cite> for details.
        <li><b>The locking page</b>. The database page that starts at
            byte offset 2<sup>30</sup>, if it is large enough to contain
            such a page, is always left unused.
      </ul>

          [fancyformat_import_requirement H30200]
          [fancyformat_import_requirement H30210]
          [fancyformat_import_requirement H30220]
        

    [h3 "The Schema Table" schema_table]
      <p>
        Apart from being the page that contains the file-header, page 1 of
        a database image is special because it is the root page of the
        B-Tree structure that contains the schema table data. From the SQL

        [Tr]<td>index <td>i1 <td>abc <td>3 <td>CREATE INDEX i1 ON abc(b, c)
        [Tr]<td>table <td>def <td>def <td>4 <td>CREATE TABLE def(a PRIMARY KEY, b, c, UNIQUE(b, c))
        [Tr]<td>index <td>sqlite_autoindex_def_1 <td>def <td>5 <td>
        [Tr]<td>index <td>sqlite_autoindex_def_2 <td>def <td>6 <td>
        [Tr]<td>view <td>v1 <td>v1 <td>0 <td>CREATE VIEW v1 AS SELECT * FROM abc
      </table>

          [fancyformat_import_requirement H30230]
          [fancyformat_import_requirement H30240]

      <p>The following requirements describe "table" records.

          [fancyformat_import_requirement H30250]
          [fancyformat_import_requirement H30260]
          [fancyformat_import_requirement H30270]
          [fancyformat_import_requirement H30280]
          [fancyformat_import_requirement H30290]
          [fancyformat_import_requirement H30300]
          [fancyformat_import_requirement H30310]

      <p>The following requirements describe "implicit index" records.

          [fancyformat_import_requirement H30320]
          [fancyformat_import_requirement H30330]
          [fancyformat_import_requirement H30340]
          [fancyformat_import_requirement H30350]

      <p>The following requirements describe "explicit index" records.

          [fancyformat_import_requirement H30360]
          [fancyformat_import_requirement H30370]
          [fancyformat_import_requirement H30380]
          [fancyformat_import_requirement H30390]

      <p>The following requirements describe "view" records.

          [fancyformat_import_requirement H30400]
          [fancyformat_import_requirement H30410]
          [fancyformat_import_requirement H30420]
          [fancyformat_import_requirement H30430]

      <p>The following requirements describe "trigger" records.

          [fancyformat_import_requirement H30440]
          [fancyformat_import_requirement H30450]
          [fancyformat_import_requirement H30460]
          [fancyformat_import_requirement H30470]

      <p>The following requirements describe the placement of B-Tree root 
         pages in auto-vacuum databases.

          [fancyformat_import_requirement H30480]
          [fancyformat_import_requirement H30490]

 
  [h2 "B-Tree Structures" "btree_structures"]
    <p>
      A large part of any SQLite database file is given over to one or more
      B-Tree structures. A single B-Tree structure is stored using one or more
      database pages. Each page contains a single B-Tree node.

          B-Tree structures are described in detail in section 
          <cite>table_btrees</cite>.
      <li>The <b>index B-Tree</b>, which uses database records as keys. Index
          B-Tree structures are described in detail in section 
          <cite>index_btrees</cite>.
    </ul>

          [fancyformat_import_requirement H30500]
          [fancyformat_import_requirement H30510]

    [h3 "Variable Length Integer Format" "varint_format"]
      <p>
        In several parts of the B-Tree structure, 64-bit twos-complement signed
        integer values are stored in the "variable length integer format"
        described here.
      <p>

        [Tr]<td>200815 <td>0x000000000003106F <td>0x8C 0xA0 0x6F
        [Tr]<td>-1     <td>0xFFFFFFFFFFFFFFFF 
            <td>0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF
        [Tr]<td>-78506 <td>0xFFFFFFFFFFFECD56
            <td>0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFD 0xCD 0x56
      </table>

          [fancyformat_import_requirement H30520]
          [fancyformat_import_requirement H30530]
          [fancyformat_import_requirement H30540]
          [fancyformat_import_requirement H30550]
      

    [h3 "Database Record Format" "record_format"]
      <p>
        A database record is a blob of data that represents an ordered
        list of one or more SQL values. Database records are used in two
        places in SQLite database files - as the associated data for entries

        the length of the data field is as described in the table above.
      <p>
        The data field associated with a string value contains the string
        encoded using the database encoding, as defined in the database
        header (see section <cite>database_header</cite>). No 
        nul-terminator character is stored in the database.

          [fancyformat_import_requirement H30560]
          [fancyformat_import_requirement H30570]
          [fancyformat_import_requirement H30580]
          [fancyformat_import_requirement H30590]
          [fancyformat_import_requirement H30600]
          [fancyformat_import_requirement H30610]
          [fancyformat_import_requirement H30620]
          [fancyformat_import_requirement H30630]
          [fancyformat_import_requirement H30640]
          [fancyformat_import_requirement H30650]
          [fancyformat_import_requirement H30660]
          [fancyformat_import_requirement H30670]
          [fancyformat_import_requirement H30680]
          [fancyformat_import_requirement H30690]
          [fancyformat_import_requirement H30700]

      <p>
        The following database file properties define restrictions on the 
        integer values that may be stored within a 
        <i>database record header</i>.

          [fancyformat_import_requirement H30710]
          [fancyformat_import_requirement H30720]

    [h3 "Index B-Trees" index_btrees]
      <p>
        As specified in section <cite>fileformat_overview</cite>, index 
        B-Tree structures store a unique set of the database records described
        in the previous section. While in some cases, when there are very
        few entries in the B-Tree, the entire structure may fit on a single

        Figure <cite>figure_indextree</cite> depicts one possible record
        distribution for an index B-Tree containing records R1 to R26, assuming
        that for all values of N, <i>R(N+1)&gt;R(N)</i>. In total the B-Tree
        structure uses 11 database file pages. Internal tree nodes contain
        database records and references to child node pages. Leaf nodes contain
        database records only.

          [fancyformat_import_requirement H30730]
          [fancyformat_import_requirement H30740]
          [fancyformat_import_requirement H30750]
          [fancyformat_import_requirement H30760]

      <p>
        The precise way in which index B-Tree pages and cells are formatted is
        described in subsequent sections.


        [h4 "Index B-Tree Content"]
          <p>
            The database file contains one index B-Tree for each database index
            in the logical database, including those created by UNIQUE or
            PRIMARY KEY clauses in table declarations. Each record stored in
            an index B-Tree contains the same number of fields, the number of
            indexed columns in the database index declaration plus one. 
          <p>
            An index B-Tree contains an entry for each row in its associated
            database table. The fields of the record used as the index B-Tree
            key are copies of each of the indexed columns of the associated 
            database row, in order, followed by the rowid value of the same 
            row. See figure <cite>figure_examplepop</cite> for an example.

          [fancyformat_import_requirement H30770]
          [fancyformat_import_requirement H30780]
          [fancyformat_import_requirement H30790]
          [fancyformat_import_requirement H30800]
 
      [h4 "Record Sort Order" "index_btree_compare_func"]
        <p>
          This section defines the comparison function used when database
          records are used as B-Tree keys for index B-Trees. The comparison
          function is only defined when both database records contain the same
          number of fields.

            block contain the total size of the free block in bytes, stored
            as a 2 byte big-endian unsigned integer.
      </ul>

      <p class=todo>
        The list of free blocks is kept in order, sorted by offset. Right?

          [fancyformat_import_requirement H30810]
          [fancyformat_import_requirement H30820]

      <p>
        The following requirements describe the <i>B-Tree page header</i>
        present at the start of both index and table B-Tree pages.

          [fancyformat_import_requirement H30830]
          [fancyformat_import_requirement H30840]
          [fancyformat_import_requirement H30850]
          [fancyformat_import_requirement H30860]

      <p>
        This requirement describes the cell content offset array. It applies
        to both B-Tree variants.

          [fancyformat_import_requirement H30870]
          [fancyformat_import_requirement H30880]
          [fancyformat_import_requirement H30890]
          [fancyformat_import_requirement H30900]
          [fancyformat_import_requirement H30910]

      <p>
        The following requirements govern management of free-space within the
        page content area (both table and index B-Tree pages).

          [fancyformat_import_requirement H30920]
          [fancyformat_import_requirement H30930]
          [fancyformat_import_requirement H30940]
          [fancyformat_import_requirement H30950]
          [fancyformat_import_requirement H30960]

      [h4 "Index B-Tree Cell Format" index_btree_cell_format]
        <p> 
          For index B-Tree internal tree node pages, each B-Tree cell begins
          with a child page-number, stored as a 4-byte big-endian unsigned
          integer. This field is omitted for leaf pages, which have no 
          children.

          in bytes less the number of unused bytes left at the end of every
          page (as read from byte offset 20 of the database header), and
          <i>max-embedded-fraction</i> and <i>min-embedded-fraction</i> are
          the values read from byte offsets 21 and 22 of the database header,
          respectively.
        [Figure indexlongrecord.gif figure_indexlongrecord "Large Record Index B-Tree Cell"]

          [fancyformat_import_requirement H30970]
          [fancyformat_import_requirement H30980]
          [fancyformat_import_requirement H30990]
          [fancyformat_import_requirement H31000]
          [fancyformat_import_requirement H31010]

      <p>
        Requirements H31010 and H30990 are similar to the algorithms 
        presented in the text above. However instead of 
        <i>min-embedded-fraction</i> and <i>max-embedded-fraction</i> the
        requirements use the constant values 32 and 64, as well-formed 
        database files are required by H30080 and H30070 to store these 

        Figure <cite>figure_tabletree</cite> depicts a table B-Tree containing
        a contiguous set of 14 integer keys starting with 1. Each key <i>n</i>
        has an associated database record R<i>n</i>. All the keys and their
        associated records are stored in the leaf pages. The internal node
        pages contain no database data, their only purpose is to provide
        a way to navigate the tree structure.

          [fancyformat_import_requirement H31020]
          [fancyformat_import_requirement H31030]
          [fancyformat_import_requirement H31040]
          [fancyformat_import_requirement H31050]

      <p class=todo>
        The special case for root page 1. Root page 1 may contain zero cells,
        just a right-child pointer to the only other b-tree page in the tree.

      <p>
        The precise way in which table B-Tree pages and cells are formatted is

          are SQL NULL. If the schema layer file-format is greater than
          2, then the values associated with the "missing" fields are 
          determined by the default value of the associated database table 
          columns.
          <span class=todo>Reference to CREATE TABLE syntax. How are default
          values determined?</span>

          [fancyformat_import_requirement H31060]
          [fancyformat_import_requirement H31070]
          [fancyformat_import_requirement H31080]
          [fancyformat_import_requirement H31090]

        <p>The following database properties discuss table B-Tree records 
           with implicit (default) values.

          [fancyformat_import_requirement H31100]
          [fancyformat_import_requirement H31110]
          [fancyformat_import_requirement H31120]

      [h4 "Table B-Tree Page Format"]
        <p>
          Table B-Tree structures use the same page format as index B-Tree 
          structures, described in section <cite>index_btree_page_format</cite>,
          with the following differences:
        <ul>
          <li>The first byte of the page-header, the "flags" field, is set to 
              0x05 for internal tree node pages, and 0x0D for leaf pages.
          <li>The content and format of the B-Tree cells is different. See
              section <cite>table_btree_cell_format</cite> for details.
          <li>The format of page 1 is the same as any other table B-Tree,
              except that 100 bytes less than usual is available for content.
              The first 100 bytes of page 1 is consumed by the database
              header.
        </ul>

          [fancyformat_import_requirement H31130]
          [fancyformat_import_requirement H31140]
        
      <p>
        Most of the requirements specified in section 
        <cite>index_btree_page_format</cite> also apply to table B-Tree 
        pages. The wording of the requirements make it clear when this is
        the case, either by refering to generic "B-Tree pages" or by
        explicitly stating that the statement applies to both "table and

          header).

        <p>
          The following requirements describe the format of table B-Tree 
          cells, and the distribution thereof between B-Tree and overflow
          pages.

          [fancyformat_import_requirement H31150]
          [fancyformat_import_requirement H31160]
          [fancyformat_import_requirement H31170]
          [fancyformat_import_requirement H31180]
          [fancyformat_import_requirement H31190]
        
        <p>
          Requirement H31190 is very similar to the algorithm presented in
          the text above. Instead of <i>min-embedded-fraction</i>, it uses
          the constant value 32, as well-formed database files are required
          by H30090 to store this value in the relevant database file 
          header field.

      <p>
        Each overflow page except for the last one in the linked list 
        contains <i>available-space</i> bytes of record data. The last
        page in the list contains the remaining data, starting at byte
        offset 4. The value of the "next page" field on the last page
        in an overflow chain is undefined.

          [fancyformat_import_requirement H31200]
          [fancyformat_import_requirement H31210]
          [fancyformat_import_requirement H31220]
          [fancyformat_import_requirement H31230]

  [h2 "The Free Page List" free_page_list]
    <p>
      Sometimes, after deleting data from the database, SQLite removes pages
      from B-Tree structures. If these pages are not immediately required
      for some other purpose, they are placed on the free page list. The
      free page list contains those pages that are not currently being

    <p>
      All trunk pages in the free-list except for the first contain the 
      maximum possible number of references to leaf pages. <span class=todo>Is this actually true in an auto-vacuum capable database?</span> The page number
      of the first page in the linked list of free-list trunk pages is 
      stored as a 4-byte big-endian unsigned integer at offset 32 of the
      database header (section <cite>database_header</cite>).

          [fancyformat_import_requirement H31240]
          [fancyformat_import_requirement H31250]
          [fancyformat_import_requirement H31260]
          [fancyformat_import_requirement H31270]
          [fancyformat_import_requirement H31280]
          [fancyformat_import_requirement H31290]
          [fancyformat_import_requirement H31300]

    <p>The following statements govern the two 4-byte big-endian integers
       associated with the <i>free page list</i> structure in the database
       header.

          [fancyformat_import_requirement H31310]
          [fancyformat_import_requirement H31320]
  

  [h2 "Pointer Map Pages" pointer_map_pages]
    <p>
      Pointer map pages are only present in auto-vacuum capable databases.
      A database is an auto-vacuum capable database if the value stored 
      at byte offset 52 of the file-header is non-zero.

      table entries for the <i>num-entries</i> pages that follow it in the
      database file:
    <pre>
        <i>pointer-map-page-number</i> := 2 + <i>n</i> * <i>num-entries</i>
</pre>


          [fancyformat_import_requirement H31330]
          [fancyformat_import_requirement H31340]
          [fancyformat_import_requirement H31350]
          [fancyformat_import_requirement H31360]
          [fancyformat_import_requirement H31370]

    <p>
      The following requirements govern the content of pointer-map entries.

          [fancyformat_import_requirement H31380]
          [fancyformat_import_requirement H31390]
          [fancyformat_import_requirement H31400]
          [fancyformat_import_requirement H31410]
          [fancyformat_import_requirement H31420]

[h1 "Database File-System Representation" file_system_usage]

    <p>
      The previous section, section <cite>database_file_format</cite> 
      describes the format of an SQLite database image. A database
      image is the serialized form of a logical SQLite database. Normally,

    [Figure journal_format.gif figure_journal_format "Journal File Format"]

    <p>
      The following requirements define a well-formed journal section. This concept
      is used in section <cite>reading_from_files</cite>. 

        [fancyformat_import_requirement H32210]
        [fancyformat_import_requirement H32220]
        [fancyformat_import_requirement H32230]
        [fancyformat_import_requirement H32240]

    <p>
      Note that a journal section that is not strictly speaking a well-formed
      journal section often contains important data. For example, many journal 
      files created by SQLite that consist of a single journal section and no
      master journal pointer contain a journal section that is not well-formed
      according to requirement H32240. See section <cite>reading_from_files</cite> 

      is defined as a blob of 28 bytes for which the journal magic field is set
      correctly and for which both the page size and sector size fields are set
      to power of two values greater than 512. Because there are no
      restrictions on the values that may be stored in the record count,
      checksum initializer or database page count fields, they do not enter
      into the definition of a well-formed journal header.

      [fancyformat_import_requirement H32090]
      [fancyformat_import_requirement H32180]
      [fancyformat_import_requirement H32190]
      [fancyformat_import_requirement H32200]

  [h4 "Journal Record Format" journal_record_format]

    <p>
    Each <i>journal record</i> contains the data for a single database page,
    a page number identifying the page, and a checksum value used to help
    detect journal file corruption.

    <p>
      The set of <i>journal records</i> that follow a <i>journal header</i>
      in a journal file are packed tightly together. There are no alignment 
      requirements for <i>journal records</i>.

      [fancyformat_import_requirement H32100]
      [fancyformat_import_requirement H32110]
      [fancyformat_import_requirement H32120]


  [h4 "Master Journal Pointer" master_journal_ptr]

    <p>
      If present, a master journal pointer occurs at the end of a journal file.
      There may or may not be unused space between the end of the final journal 

               Finally, the <b>journal magic</b> field always contains a
               well-known 8-byte string value; the same value stored in the
               first 8 bytes of a <i>journal header</i>. The well-known
               sequence of bytes is:
                 <pre>0xd9 0xd5 0x05 0xf9 0x20 0xa1 0x63 0xd7</pre>
    </table>

      [fancyformat_import_requirement H32140]
      [fancyformat_import_requirement H32150]
      [fancyformat_import_requirement H32160]
      [fancyformat_import_requirement H32170]

[h3 "Master-Journal File Details" masterjournal_file_format]

  <p>
    A <i>master-journal file</i> contains the full paths to two or more
    <i>journal files</i>, each encoded using UTF-8 encoding and terminated
    by a single nul character (byte value 0x00). There is no padding 

    text (point to document sections). Or, better, both.

  <p>
    These requirements describe the way a database reader must determine
    whether or not there is a valid journal file within the 
    file-system.

    [fancyformat_import_requirement H32000]
    [fancyformat_import_requirement H32010]
    [fancyformat_import_requirement H32020]

  <p>
    If there is a valid journal file within the file-system, the 
    following requirements govern how a reader should determine the set
    of valid <i>journal records</i> that it contains.

    [fancyformat_import_requirement H32250]
    [fancyformat_import_requirement H32260]
    [fancyformat_import_requirement H32270]
    [fancyformat_import_requirement H32280]

  <p>
    The following requirements dictate the way in which database
    <i>page-size</i> and the number of pages in the database image
    should be determined by the reader.

    [fancyformat_import_requirement H32030]
    [fancyformat_import_requirement H32040]
    [fancyformat_import_requirement H32050]
    [fancyformat_import_requirement H32060]

  <p>
    The following requirements dictate the way in which the data for each
    page of the database image can be located within the file-system
    by a database reader.

    [fancyformat_import_requirement H32070]
    [fancyformat_import_requirement H32080]

[h1 "SQLite Interoperabilty Requirements" interoperability_requirements]

  <p>
    This section contains requirements that further constrains the behaviour
    of software that accesses (reads and/or writes) SQLite databases stored
    within the file-system. These requirements need only be implemented by

    because free-list leaf pages contain no valid data and are never read
    by SQLite database readers. Since the blob of data stored on such a
    page is never read for any purpose, two database images may have a
    different blob stored on a free-list leaf page and still be considered
    equivalent. This concept can sometimes be exploited to more efficiently
    update an SQLite database file-system representation.

    [fancyformat_import_requirement H32290]

  <p>
    The following requirement constrains the way in which a database 
    file-system representation may be updated. In many ways, it is
    equivalent to "do not corrupt the database file-system representation
    under those conditions where the file-system should not be corrupted".
    The definition of "handled failure" depends on the mode that SQLite
    is running in (or on the requirements of the external system accessing
    the database file-system representation).

    [fancyformat_import_requirement H32300]

  <p>
    The following two sections, <cite>rollback_journal_method</cite>
    and <cite>atomic_write_method</cite>, are somewhat advisory in nature.
    They contain descriptions of two different methods used by SQLite to
    modify a database image within a database file-system representation in
    accordance with the above requirements. They are not the only methods

    a journal file is set to contain the original database page-size and 
    page-count and written to non-volatile storage before the size of the
    database file is modified. And that once the size of the database file has
    been modified, the journal header does not become unstable and the page-size 
    and page-count values stored therein are not modified until the end of
    the transaction.

       [fancyformat_import_requirement H32320]
       [fancyformat_import_requirement H32330]

  <p>
    Journal before overwrite:

       [fancyformat_import_requirement H32340]
       [fancyformat_import_requirement H32350]

  <p>
    Journal before truncate:

       [fancyformat_import_requirement H32360]
       [fancyformat_import_requirement H32370]
      

  h4 "Multiple Database Transactions" multi_db_transactions

  <p>
    SQLite is required 
    to do make all modifications associated with the transaction such that 

    </table>
      
    <p>
      The most important types of locks are SHARED and EXCLUSIVE. Before any 
      part of the database file is read, a database client must obtain a SHARED 
      lock or greater.

    [fancyformat_import_requirement H33000]

    <p>
      Before the database file may be written to, a database client must
      be holding an EXCLUSIVE lock. Because holding an EXCLUSIVE lock 
      guarantees that no other client is holding a SHARED lock, it also
      guarantees that no other client may be reading from the database file
      as it is being written.

    [fancyformat_import_requirement H33010]

    <p>
      The two requirements above govern reading from and writing to the
      database file. In order to write to a journal file, a database client
      must obtain at least a RESERVED lock.

    [fancyformat_import_requirement H33020]

    <p>
      The requirement above implies that a database writer may write to the
      journal file at the same time as a reader is reading from the database
      file. This improves concurrency in environments that feature multiple
      clients, as a database writer may perform part of its IO before locking
      the database file-system representation with an EXCLUSIVE lock. In order

           database reader to assume that the contents of the database file
           represents the current database image.
    </ul>

    <p>
      The following requirements formally restate the above bullet points.

    [fancyformat_import_requirement H33030]
    [fancyformat_import_requirement H33060]
    [fancyformat_import_requirement H33080]

  [h2 "SQLite Database Header Cookie Protocol" database_header_cookies_protocol]

    <p>
      While a database reader is holding a SHARED lock on the database
      file-system representation, it may freely cache data in main memory
      since there is no way that another client can modify the database

      an EXCLUSIVE lock, then each header value need only be updated once, as
      part of the first image modification that modifies the associated class
      of data. Specifically, the change counter field need only be incremented
      as part of the first image modification that takes place, and the 
      database schema version need only be incremented as part of the first
      modification that includes a schema change. 

    [fancyformat_import_requirement H33040]
    [fancyformat_import_requirement H33050]
    [fancyformat_import_requirement H33070]


[h1 References]






  <table id="refs" style="width:auto; margin: 1em 5ex">
  [Ref 1 ref_comer_btree {
     Douglas Comer, <u>Ubiquitous B-Tree</u>, ACM Computing Surveys (CSUR),
     v.11 n.2, pages 121-137, June 1979.
  }]
  [Ref 2 ref_knuth_btree {
     Donald E. Knuth, <u>The Art Of Computer Programming, Volume 3:
     "Sorting And Searching"</u>, pages 473-480. Addison-Wesley
     Publishing Company, Reading, Massachusetts.
  }]
  [Ref 3 atomic_commit_page {
    SQLite Online Documentation,<u>How SQLite Implements Atomic Commit</u>,
    <a href="atomiccommit.html">http://www.sqlite.org/atomiccommit.html</a>.
  }]
  </table>

}
</tcl>