Documentation Source Text

fancyformat_document "SQLite B-Tree Module" {hlr50000.txt llr50000.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.
................................................................................
                      sqlite3BtreePrevious sqlite3BtreeEof]

      [btree_api_defn sqlite3BtreeKeySize sqlite3BtreeKey sqlite3BtreeKeyFetch \
                      sqlite3BtreeDataFetch sqlite3BtreeDataSize sqlite3BtreeData]

      [btree_api_defn sqlite3BtreeCount]






      [btree_api_defn sqlite3BtreeMovetoUnpacked]











      <p class=todo>
	Not clear how to deal with these. Define an external module to
	encapsulate these and define sorting order etc.? That's tricky as things are
	because the UnpackedRecord.flags field defines the "search mode" used
        by sqlite3BtreeMovetoUnpacked.

................................................................................

      [btree_api_defn sqlite3BtreeCreateTable]

      [btree_api_defn BTREE_INTKEY BTREE_ZERODATA BTREE_LEAFDATA]

      [btree_api_defn sqlite3BtreeDropTable sqlite3BtreeClearTable sqlite3BtreeUpdateMeta]


      [btree_api_defn sqlite3BtreeDelete sqlite3BtreeInsert sqlite3BtreeCursorHasMoved sqlite3BtreePutData]




      [btree_api_defn sqlite3BtreeIncrVacuum]







































    [h2 "What do these do?"]

    <p class=todo>
      The following is used only from within VdbeExec() to check whether or not
      a cursor was opened on a table or index b-tree. Corruption tests can move into
      the b-tree layer.

................................................................................
    <li> sqlite3PagerBackupPtr
  </ul>
</ul>


  [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.
   




    [h3 "B-Tree Insert"]
    [h3 "B-Tree Delete"]
    [h3 "B-Tree Balancing Algorithm"]



     <ul>
       <li><p>The <b>balance deeper</b> sub-algorithm is used when the root page of
           a b-tree is overfull. It creates a new page and copies the
           entire contents of the overfull root page to it. The root page
           is then zeroed and the new page installed as its only child.
           The balancing algorithm is then run on the new child page (in case
................................................................................
      </ol>

      [Figure btreemodule_balance_deeper.svg figure_balance_deeper "Example Balance Deeper Transform"]

    [h4 "Balance Shallower"]

      <ol>
        <li> Copy page data from child-page to root-page.
        <li> Fix pointer map entries associated with new root-page content.
        <li> Move child-page to database image free-list.
      </ol>

      [Figure btreemodule_balance_shallower.svg figure_balance_shallower "Example Balance Shallower Transform"]

    [h4 "Balance Quick"]
................................................................................
        <li> Execute the balance procedure on the parent page.
      </ol>

      [Figure btreemodule_balance_quick.svg figure_balance_quick "Example Balance Quick Transform"]

    [h4 "Balance Siblings" balance_siblings]

      [fancyformat_import_requirement L50001]

    <p class=todo>
      The following description describes how balance() is to be implemented. This
      represents (I think) the lowest level of detail that should be in this document.
      One skilled in the art could use this description to reimplement SQLite's
      balance-siblings algorithm. We also need requirements at a higher level
      of detail in this section. Something to test!
................................................................................
               has moved from one page to another the pointer-map entry associated with
               the cell's child page must be updated.
          <li> If the page being balanced is (was) not a leaf, then the pointer-map entry
               associated with each sibling's right-child page may need to be updated.
        </ol>
      </ol>

  [h3 "Page Allocation and Deallocation"]

     <p class=todo>
       Amongst other things, this section needs to explain our old pals the
       DontWrite() and DontRollback() optimizations.




  [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

fancyformat_document "SQLite B-Tree Module" {hlr50000.txt llr50000.txt} {

  [h1 "Document Overview"]

  [h2 "Scope and Purpose"]

  <p>
    This document provides a description of the functionality of and public 
    interface offered by the SQLite b-tree module. It also, to a certain extent,
    describes the algorithm and implementation techniques used internally by
    the module. 

  <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.
................................................................................
                      sqlite3BtreePrevious sqlite3BtreeEof]

      [btree_api_defn sqlite3BtreeKeySize sqlite3BtreeKey sqlite3BtreeKeyFetch \
                      sqlite3BtreeDataFetch sqlite3BtreeDataSize sqlite3BtreeData]

      [btree_api_defn sqlite3BtreeCount]

    [h3 sqlite3BtreeMovetoUnpacked]

      <p>
        The sqlite3BtreeMovetoUnpacked function is used to 

      [btree_api_defn sqlite3BtreeMovetoUnpacked]

      <p>
        The following requirements specify exactly how a b-tree cursor is to be moved
        by a successful call to sqlite3BtreeMovetoUnpacked.

      [fancyformat_import_requirement L50008]
      [fancyformat_import_requirement L50009]
      [fancyformat_import_requirement L50010]
      [fancyformat_import_requirement L50011]


      <p class=todo>
	Not clear how to deal with these. Define an external module to
	encapsulate these and define sorting order etc.? That's tricky as things are
	because the UnpackedRecord.flags field defines the "search mode" used
        by sqlite3BtreeMovetoUnpacked.

................................................................................

      [btree_api_defn sqlite3BtreeCreateTable]

      [btree_api_defn BTREE_INTKEY BTREE_ZERODATA BTREE_LEAFDATA]

      [btree_api_defn sqlite3BtreeDropTable sqlite3BtreeClearTable sqlite3BtreeUpdateMeta]

      [btree_api_defn sqlite3BtreeDelete]
      [btree_api_defn sqlite3BtreeCursorHasMoved sqlite3BtreePutData]
      [btree_api_defn sqlite3BtreeIncrVacuum]

      [h3 sqlite3BtreeInsert]

        [btree_api_defn sqlite3BtreeInsert]

        [fancyformat_import_requirement L50001]

      <p class=todo>
        Or, if an entry with the specified key exists, it shall be replaced.

      <p class=todo>
        Malloc and IO error handling. Maybe these should be grouped together
        for a whole bunch of APIs. And hook into the above via a defintion of
        "successful call".

      <p>
        The requirement above implies that the results of passing anything else as 
        the first argument to sqlite3BtreeInsert, for example a read-only b-tree cursor,
        are undefined.

        [fancyformat_import_requirement L50002]
        [fancyformat_import_requirement L50003]
        [fancyformat_import_requirement L50004]

      <p>
        The following requirements describe the seventh and eighth paramaters passed
        to the sqlite3BtreeInsert function. Both of these are used to provide extra
        information used by sqlite3BtreeInsert to optimize the insert operation. They
        may be safely ignored by alternative b-tree implementations.

      <p class=todo>
        There should be some rationalization for these, eventually. Some tracebility
        from somewhere to show how the b-tree module offering these slightly esoteric
        interfaces is helpful to SQLite overall.

        [fancyformat_import_requirement L50005]
        [fancyformat_import_requirement L50006]

      <p>
        If a non-zero value is passed as the eighth parameter to sqlite3BtreeInsert 
        and the b-tree cursor has not been positioned as assumed by L50006, the
        results are undefined.

    [h2 "What do these do?"]

    <p class=todo>
      The following is used only from within VdbeExec() to check whether or not
      a cursor was opened on a table or index b-tree. Corruption tests can move into
      the b-tree layer.

................................................................................
    <li> sqlite3PagerBackupPtr
  </ul>
</ul>


  [h1 "Module Implementation"]

  [h2 "Database Image Traversal"] 

  [h2 "Database Image 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 the b-tree 

       balancing works, deleting an internal cell from an index b-tree etc.

    [h3 "Creating a B-Tree Structure"]
    [h3 "Clearing a B-Tree Structure"]
    [h3 "Deleting a B-Tree Structure"]
   
    [h3 "B-Tree Insert/Replace Entry"]
    [h3 "B-Tree Delete Entry"]


    [h3 "B-Tree Balancing Algorithm"]

     <ul>
       <li><p>The <b>balance deeper</b> sub-algorithm is used when the root page of
           a b-tree is overfull. It creates a new page and copies the
           entire contents of the overfull root page to it. The root page
           is then zeroed and the new page installed as its only child.
           The balancing algorithm is then run on the new child page (in case
................................................................................
      </ol>

      [Figure btreemodule_balance_deeper.svg figure_balance_deeper "Example Balance Deeper Transform"]

    [h4 "Balance Shallower"]

      <ol>
        <li> Copy node data from child-page to root-page.
        <li> Fix pointer map entries associated with new root-page content.
        <li> Move child-page to database image free-list.
      </ol>

      [Figure btreemodule_balance_shallower.svg figure_balance_shallower "Example Balance Shallower Transform"]

    [h4 "Balance Quick"]
................................................................................
        <li> Execute the balance procedure on the parent page.
      </ol>

      [Figure btreemodule_balance_quick.svg figure_balance_quick "Example Balance Quick Transform"]

    [h4 "Balance Siblings" balance_siblings]

      [fancyformat_import_requirement L51001]

    <p class=todo>
      The following description describes how balance() is to be implemented. This
      represents (I think) the lowest level of detail that should be in this document.
      One skilled in the art could use this description to reimplement SQLite's
      balance-siblings algorithm. We also need requirements at a higher level
      of detail in this section. Something to test!
................................................................................
               has moved from one page to another the pointer-map entry associated with
               the cell's child page must be updated.
          <li> If the page being balanced is (was) not a leaf, then the pointer-map entry
               associated with each sibling's right-child page may need to be updated.
        </ol>
      </ol>

    [h3 "Page Allocation and Deallocation"]

     <p class=todo>
       Amongst other things, this section needs to explain our old pals the
       DontWrite() and DontRollback() optimizations.




  [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

}
proc fancyformat_import_requirement {reqid} {
  lappend ::Requirements $reqid
  set ret "<p class=req id=$reqid><span>[lindex $::ffreq($reqid) 1]</span>"
  if {[llength [lindex $::ffreq($reqid) 0]]} {
    append ret " (P: [lindex $::ffreq($reqid) 0])"
  } 



  append ret "</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>

}
proc fancyformat_import_requirement {reqid} {
  lappend ::Requirements $reqid
  set ret "<p class=req id=$reqid><span>[lindex $::ffreq($reqid) 1]</span>"
  if {[llength [lindex $::ffreq($reqid) 0]]} {
    append ret " (P: [lindex $::ffreq($reqid) 0])"
  } 
  if {[info exists ::ffreq_children($reqid)]} {
    append ret " (C: $::ffreq_children($reqid))"
  } 
  append ret "</p>"
}

set ::Requirements [list]

proc fancyformat_document {zTitle lReqfile zBody} {
  unset -nocomplain ::ffreq
  unset -nocomplain ::ffreq_children
  foreach f $lReqfile {
    hd_read_requirement_file $::DOC/req/$f ::ffreq
  }
  foreach req [array names ::ffreq] {
    foreach parent [lindex $::ffreq($req) 0] {
      lappend ::ffreq_children($parent) $req
    }
  }


  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>

HLR L50001

















































The balance-siblings algorithm shall redistribute the b-tree cells currently 
stored on a overfull or underfull page and up to two sibling pages, adding
or removing siblings as required, such that no sibling page is overfull and
the minimum possible number of sibling pages is used to store the 
redistributed b-tree cells.


HLR L50002 L50001
The new pages 

HLR L50001  H50128
A successful call to the sqlite3BtreeInsert function made with a read/write
b-tree cursor passed as the first argument shall insert a new entry into the
b-tree structure the b-tree cursor is open on.

HLR L50002  H50128
If the b-tree cursor passed to sqlite3BtreeInsert as the first argument is
open on a table b-tree, then the values passed as the second parameter (pKey) 
shall be ignored. The value passed as the third parameter (nKey) shall be
used as the integer key for the new entry.

HLR L50003  H50128
If the b-tree cursor passed to sqlite3BtreeInsert as the first argument is
open on a table b-tree, then the database record associated with the new entry
shall consist of a copy of the first nData bytes of the buffer pointed to by pData 
followed by nZero zero (0x00) bytes, where pData, nData and nZero are the
fourth, fifth and sixth parameters passed to sqlite3BtreeInsert, respectively.

HLR L50004  H50128
If the b-tree cursor passed to sqlite3BtreeInsert as the first argument is
open on an index b-tree, then the values passed as the fourth, fifth and sixth
parameters shall be ignored. The key (a database record) used by the new entry 
shall consist of the first nKey bytes of the buffer pointed to by pKey, where
pKey and nKey are the second and third parameters passed to sqlite3BtreeInsert,
respectively.

HLR L50005
If the value passed as the seventh parameter to a call to sqlite3BtreeInsert
is non-zero, sqlite3BtreeInsert shall interpret this to mean that it is likely
(but not certain) that the key belonging to the new entry is larger than the
largest key currently stored in the b-tree structure, and optimize accordingly.

HLR L50006
If the value passed as the eighth parameter to a call to sqlite3BtreeInsert
is non-zero, then the B-Tree module shall interpret this to mean that the
the b-tree cursor has already been positioned by a successful call to 
sqlite3BtreeMovetoUnpacked specifying the same key value as is being inserted,
and that sqlite3BtreeMovetoUnpacked has set the output value required by L50011 to
this value.



HLR L50008
If a call is made to sqlite3BtreeMovetoUnpacked specifying a key value for 
which there exists an entry with a matching key value in the b-tree structure,
the b-tree cursor shall be moved to point to this entry. In this case *pRes
(the value of the "int" variable pointed to by the pointer passed as the
fifth parameter to sqlite3BtreeMovetoUnpacked) shall be set to 0 before
returning.

HLR L50009
If a call is made to sqlite3BtreeMovetoUnpacked specifying a key value for
which there does not exist an entry with a matching key value in the b-tree
structure, the b-tree cursor shall be moved to point to an entry located
on the leaf page that would contain the requested entry, were it present.

HLR L50010
If the condition specified in L50009 is met and the b-tree structure 
contains one or more entries (is not empty), the b-tree cursor shall be left
pointing to an entry that would lie adjacent (immediately before or after in
order by key) to the requested entry on the leaf page, were it present.

HLR L50011
If the condition specified in L50009 is met and the b-tree cursor is left
pointing to an entry with a smaller key than that requested, or the cursor
is left pointing a no entry at all because the b-tree structure is completely
empty, *pRes (the value of the "int" variable pointed to by the pointer passed
as the fifth parameter to sqlite3BtreeMovetoUnpacked) shall be set to -1.
Otherwise, if the b-tree cursor is left pointing to an entry with a larger key
than that requested, *pRes shall be set to 1.





HLR L51001
The balance-siblings algorithm shall redistribute the b-tree cells currently 
stored on a overfull or underfull page and up to two sibling pages, adding
or removing siblings as required, such that no sibling page is overfull and
the minimum possible number of sibling pages is used to store the 
redistributed b-tree cells.