Documentation Source Text

           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.

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

      <ol>
        <li> Allocate a new page (the new sibling-page).

        <li> Populate the new sibling page with the new b-tree entry.

	<li> Add a new divider cell to the parent. The divider cell contains a

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

    <p>
      The balance-siblings algorithm, as implemented by SQLite, is described as
      a series of steps below.  <span class=todo> there are a few terms used
      below that need definitions/clarifications.</span>

      <ol>
        <li> Determine the set of sibling pages to redistribute the cells of, using 
             the following rules:
        <ol type="a">
          <li> If the parent page has three or fewer child pages, then all child 
               pages are deemed to be sibling pages for the purposes of the balance-siblings

                immediately follows the cells stored on the page (the cell that was
                assigned to be divider cell in step 3). For the right-most sibling page,
                the right-child pointer is set to the value that was stored in the
                right-child pointer of the right-most original sibling page identified
                in step 1.
        </ol>
        <li> Populate the parent page.
        <ol type="a">
	  <li> If the page being balanced is (was) not a leaf page of a table
	       b-tree, the cells that contained pointers to the old sibling
               pages are replaced by the cells designated as divider cells as part
               of step 3. The right-child pointer field of the first divider cell
               is overwritten with the page number of the first new sibling page, and 
               so on.

	  <li> If the page being balanced is (was) a leaf page of a table
	       b-tree, the cells that contained pointers to the old sibling
               pages are replaced by a divider cell associated with all but the
               right-most sibling page. The child-page number stored in each divider
               cell is set to the page number of the associated sibling. The ingeger key 
               value stored in each divider cell is a copy of the largest integer key
               value stored on the associated sibling page.

	  <li> Before balancing, the parent page contained a pointer to the right-most
               sibling page, either as part of a cell or as the right-child pointer
               stored in the page header. Either way, this value must be overwritten
               with the page number of the new right-most sibling page.
               
        </ol>

        <li> Populate pointer map entries.
        <ol type="a">
          <li> For each sibling page that was not also an original sibling page, the
               associated pointer-map entry must be updated. Similarly, the pointer-map
               entry associated with each original sibling page that is no longer a
               sibling page must be updated.
          <li> For each cell containing an overflow pointer that has been moved from one 
               page to another, the pointer-map entry associated with the overflow page 
               must be updated.
          <li> If the page being balanced is (was) not a leaf, then for each cell that
               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.