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: |
273d1c6feed6b0b35988534d5e2eabc3 |
| 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
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.
|