Documentation Source Text

Check-in [273d1c6fee]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Fill in a couple of missing details wrt balance_nonroot (balance-siblings).
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:273d1c6feed6b0b35988534d5e2eabc3767e4c5c
User & Date: dan 2009-06-09 00:52:10
Context
2009-06-09
11:58
Add a few interface requirements to btreemodule.html. check-in: 9949936e6e user: dan tags: trunk
00:55
Correct the description on how short_column_names and full_column_names interact. check-in: 787c316f3f user: drh tags: trunk
00:52
Fill in a couple of missing details wrt balance_nonroot (balance-siblings). check-in: 273d1c6fee user: dan tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to pages/btreemodule.in.

851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
...
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
...
914
915
916
917
918
919
920







921
922
923
924
925
926
927
928
929
930
931
....
1021
1022
1023
1024
1025
1026
1027







1028
1029







1030






















1031
1032
1033
1034
1035
1036
1037
           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 intkey append</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 Intkey Append"]

      <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>
      The balance-siblings algorithm 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.








        <li> Populate pointer map entries.






























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







|







 







|







 







>
>
>
>
>
>
>

|
|
|







 







>
>
>
>
>
>
>

<
>
>
>
>
>
>
>

>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
...
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
...
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
....
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042

1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
           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.