Documentation Source Text

<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!-- Created with Inkscape (http://www.inkscape.org/) -->
<svg
   xmlns:dc="http://purl.org/dc/elements/1.1/"
   xmlns:cc="http://creativecommons.org/ns#"
   xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
   xmlns:svg="http://www.w3.org/2000/svg"
   xmlns="http://www.w3.org/2000/svg"
   xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd"
   xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape"
   width="900"
   height="230.93105"
   id="svg3406"
   sodipodi:version="0.32"
   inkscape:version="0.46"
   version="1.0"
   sodipodi:docname="btreemodule_delete1.svg"
   inkscape:output_extension="org.inkscape.output.svg.inkscape">
  <defs
     id="defs3408">
    <marker
       inkscape:stockid="Arrow1Lend"
       orient="auto"
       refY="0"
       refX="0"
       id="Arrow1Lend"
       style="overflow:visible">
      <path
         id="path3355"
         d="M 0,0 L 5,-5 L -12.5,0 L 5,5 L 0,0 z"
         style="fill-rule:evenodd;stroke:#000000;stroke-width:1pt;marker-start:none"
         transform="matrix(-0.8,0,0,-0.8,-10,0)" />
    </marker>
    <inkscape:perspective
       sodipodi:type="inkscape:persp3d"
       inkscape:vp_x="0 : 526.18109 : 1"
       inkscape:vp_y="0 : 1000 : 0"
       inkscape:vp_z="744.09448 : 526.18109 : 1"
       inkscape:persp3d-origin="372.04724 : 350.78739 : 1"
       id="perspective3414" />
  </defs>
  <sodipodi:namedview
     id="base"
     pagecolor="#ffffff"
     bordercolor="#666666"
     borderopacity="1.0"
     gridtolerance="10000"
     guidetolerance="10"
     objecttolerance="10"
     inkscape:pageopacity="0.0"
     inkscape:pageshadow="2"
     inkscape:zoom="1.41"
     inkscape:cx="389.70903"
     inkscape:cy="136.54327"
     inkscape:document-units="px"
     inkscape:current-layer="layer1"
     showgrid="true"
     showguides="true"
     inkscape:guide-bbox="true"
     inkscape:window-width="1533"
     inkscape:window-height="864"
     inkscape:window-x="70"
     inkscape:window-y="0">
    <inkscape:grid
       type="xygrid"
       id="grid3416"
       visible="true"
       enabled="true" />
  </sodipodi:namedview>
  <metadata
     id="metadata3411">
    <rdf:RDF>
      <cc:Work
         rdf:about="">
        <dc:format>image/svg+xml</dc:format>
        <dc:type
           rdf:resource="http://purl.org/dc/dcmitype/StillImage" />
      </cc:Work>
    </rdf:RDF>
  </metadata>
  <g
     inkscape:label="Layer 1"
     inkscape:groupmode="layer"
     id="layer1"
     transform="translate(-119.5,-371.89945)">
    <rect
       style="fill:#80a796;fill-opacity:1;stroke:none;stroke-width:20;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:0"
       id="rect2422"
       width="20.709229"
       height="20"
       x="378.62402"
       y="402.96823" />
    <rect
       style="fill:none;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
       id="rect3420"
       width="129.91663"
       height="19.862286"
       x="299.41663"
       y="462.96823" />
    <path
       style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow1Lend);stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
       d="M 379.33326,422.96822 L 369.33326,452.96822"
       id="path4129"
       sodipodi:nodetypes="cc" />
    <path
       style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow1Lend);stroke-miterlimit:4;stroke-dasharray:8, 8;stroke-dashoffset:0;stroke-opacity:1"
       d="M 429.41663,482.83051 L 449.41663,532.83051"
       id="path3429"
       sodipodi:nodetypes="cc" />
    <rect
       style="fill:#40668b;fill-opacity:1;stroke:none;stroke-width:0.39586431;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
       id="rect4794"
       width="19.758081"
       height="20.466421"
       x="499.41663"
       y="542.83051" />
    <rect
       style="fill:none;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
       id="rect3427"
       width="129.91663"
       height="19.862286"
       x="389.5"
       y="542.9682" />
    <rect
       style="fill:none;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
       id="rect3337"
       width="129.91663"
       height="19.862286"
       x="339.41663"
       y="402.96823" />
    <rect
       style="fill:none;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
       id="rect3963"
       width="129.91663"
       height="19.862286"
       x="619.41663"
       y="463.43472" />
    <path
       style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow1Lend);stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
       d="M 699.33326,423.43467 L 689.33326,453.43467"
       id="path3965"
       sodipodi:nodetypes="cc" />
    <path
       style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow1Lend);stroke-miterlimit:4;stroke-dasharray:8, 8;stroke-dashoffset:0;stroke-opacity:1"
       d="M 749.41663,483.29696 L 769.41663,533.29696"
       id="path3967"
       sodipodi:nodetypes="cc" />
    <rect
       style="fill:#40668b;fill-opacity:1;stroke:none;stroke-width:0.39586431;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
       id="rect3969"
       width="19.758081"
       height="20.466421"
       x="699.74194"
       y="402.83051" />
    <rect
       style="fill:none;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
       id="rect3971"
       width="129.91663"
       height="19.862286"
       x="709.5"
       y="543.43463" />
    <rect
       style="fill:none;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
       id="rect3973"
       width="129.91663"
       height="19.862286"
       x="659.41663"
       y="403.43472" />
    <path
       style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
       d="M 570,372.39945 L 570,602.33049"
       id="path4816" />
    <text
       xml:space="preserve"
       style="font-size:40px;font-style:normal;font-weight:normal;line-height:125%;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1;font-family:Bitstream Vera Sans"
       x="809.5"
       y="432.83051"
       id="text4856"
       sodipodi:linespacing="125%"><tspan
         sodipodi:role="line"
         id="tspan4858"
         x="809.5"
         y="432.83051"
         style="font-size:14px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;writing-mode:lr-tb;text-anchor:start;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;font-family:Sans;-inkscape-font-specification:Sans">The blue cell has been </tspan><tspan
         sodipodi:role="line"
         x="809.5"
         y="450.33051"
         style="font-size:14px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;writing-mode:lr-tb;text-anchor:start;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;font-family:Sans;-inkscape-font-specification:Sans"
         id="tspan4002">removed from leaf node</tspan><tspan
         sodipodi:role="line"
         x="809.5"
         y="467.83051"
         style="font-size:14px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;writing-mode:lr-tb;text-anchor:start;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;font-family:Sans;-inkscape-font-specification:Sans"
         id="tspan4004">and used to replace the</tspan><tspan
         sodipodi:role="line"
         x="809.5"
         y="485.33051"
         style="font-size:14px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;writing-mode:lr-tb;text-anchor:start;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;font-family:Sans;-inkscape-font-specification:Sans"
         id="tspan4006">cell deleted from the </tspan><tspan
         sodipodi:role="line"
         x="809.5"
         y="502.83051"
         style="font-size:14px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;writing-mode:lr-tb;text-anchor:start;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;font-family:Sans;-inkscape-font-specification:Sans"
         id="tspan4008">internal node.</tspan></text>
    <text
       xml:space="preserve"
       style="font-size:40px;font-style:normal;font-weight:normal;line-height:125%;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1;font-family:Bitstream Vera Sans"
       x="129.5"
       y="502.83051"
       id="text4010"
       sodipodi:linespacing="125%"><tspan
         sodipodi:role="line"
         x="129.5"
         y="502.83051"
         style="font-size:14px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;writing-mode:lr-tb;text-anchor:start;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;font-family:Sans;-inkscape-font-specification:Sans"
         id="tspan4020">The green cell is to be deleted from</tspan><tspan
         sodipodi:role="line"
         x="129.5"
         y="520.33051"
         style="font-size:14px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;writing-mode:lr-tb;text-anchor:start;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;font-family:Sans;-inkscape-font-specification:Sans"
         id="tspan4033">an internal tree node. The blue cell</tspan><tspan
         sodipodi:role="line"
         x="129.5"
         y="537.83051"
         style="font-size:14px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;writing-mode:lr-tb;text-anchor:start;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;font-family:Sans;-inkscape-font-specification:Sans"
         id="tspan4035">is the cell with the largest key in</tspan><tspan
         sodipodi:role="line"
         x="129.5"
         y="555.33051"
         style="font-size:14px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;writing-mode:lr-tb;text-anchor:start;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;font-family:Sans;-inkscape-font-specification:Sans"
         id="tspan4037">the sub-tree headed by the </tspan><tspan
         sodipodi:role="line"
         x="129.5"
         y="572.83051"
         style="font-size:14px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;writing-mode:lr-tb;text-anchor:start;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;font-family:Sans;-inkscape-font-specification:Sans"
         id="tspan4039">child-page of the green cell.</tspan></text>
  </g>
</svg>

      [btree_api_defn sqlite3BtreeCreateTable]

      [btree_api_defn BTREE_INTKEY BTREE_ZERODATA BTREE_LEAFDATA]

      [btree_api_defn sqlite3BtreeDropTable sqlite3BtreeClearTable sqlite3BtreeUpdateMeta]


      [btree_api_defn sqlite3BtreeCursorHasMoved sqlite3BtreePutData]
      [btree_api_defn sqlite3BtreeIncrVacuum]

      [h3 sqlite3BtreeDelete sqlite3BtreeDelete]

        [btree_api_defn sqlite3BtreeDelete]

        [fancyformat_import_requirement L50013]

      <p class=todo>
        Effect of a delete operation on other cursors that are pointing to the
        deleted b-tree entry.

      <p class=todo>
        Malloc and IO error handling. Same as for sqlite3BtreeInsert.

      [h3 sqlite3BtreeInsert]

        [btree_api_defn sqlite3BtreeInsert]

        [fancyformat_import_requirement L50001]









      <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 L50012]

      <p>
	In other words, the sqlite3BtreeInsert API could easily be renamed
        sqlite3BtreeInsertOrReplace. <span class=todo>We will probably need a module
        requirement for the "replace" operation.</span>

        [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

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

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

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

       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 "Inserting, Replacing and Deleting B-Tree Entries"]

    [h4 "B-Tree Insert/Replace Entry"]

      <p>
        This section describes the way in which new entries may be inserted 
        into a b-tree structure, and how existing entries may be replaced. Both
        of these operations are accessed using the sqlite3BtreeInsert API.

    [h4 "B-Tree Delete Entry"]

      <p>
        This section describes the way in which entries may be removed from
	a b-tree structure, as required when the sqlite3BtreeDelete (section
        <cite>sqlite3BtreeDelete</cite>) API is invoked. Removing an entry
        from a b-tree table involves the following steps:

      <ol>
        <li> All overflow pages in the overflow page chain (if any) associated
             with the entry must be moved to the database free-list. If the
             database image is an autovacuum database, the pointer-map entries
             that correspond to each overflow page in the chain must be updated.
             
        <li> The b-tree cell corresponding to the entry must be removed from
             the b-tree structure.
      </ol>

      <p class=todo>
	Note about the optimization that makes it possible to move overflow pages
        to the free-list without reading their contents (i.e. without loading them
        into the cache).

      <p>
        If the b-tree entry being removed is located on a leaf page (as is always the
        case with table b-tree structures), then deleting an entry from a b-tree
        is quite simple.

      [Figure btreemodule_delete1.svg figure_delete1 "Delete from an Internal Node"]

    [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
           it is overfull).

       <li><p>The <b>balance shallower</b> sub-algorithm is used when the root page 
           of a b-tree has only a single child page. If possible, the data from
           the child page is copied into the root-page and the child page discarded.

       <li><p>The <b>balance quick</b> sub-algorithm is used in a very specific,
           but common scenario. It is used only for table b-trees, when a new entry that
           has a key value greater than all existing keys in the b-tree is inserted and
           causes the right-most leaf page of the b-tree structure to become overfull.

       <li><p>The <b>balance siblings</b> sub-algorithm is run when a b-tree page that
           is not the root-page of its b-tree structure is either overfull or underfull.




     </ul>

    [h4 "Balance Deeper"]
      <ol>

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 L50012  H50128
If a call to sqlite3BtreeInsert is made to insert an entry specifying a key
value for which there already exists a matching key within the b-tree
structure, the entry with the matching key shall be removed from the b-tree
structure before the new entry is inserted.


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.

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 L50013  H50127
A successful call to the sqlite3BtreeDelete function made with a read/write
b-tree cursor passed as the first argument shall remove the entry pointed to by
the b-tree cursor from the b-tree structure. 



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.