Documentation Source Text

Check-in [982ca6b660]
Login

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

Overview
Comment:Add a few lines to btreemodule.html.
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:982ca6b660578463a76556c87cbf44d58e203aa9
User & Date: dan 2009-06-08 06:23:13
Context
2009-06-08
13:39
Begin preparing the website for the 3.6.15 release. check-in: 4b07b4204a user: drh tags: trunk
12:57
Fix typos in the privatebranch document. check-in: dea8397e9a user: drh tags: trunk
06:23
Add a few lines to btreemodule.html. check-in: 982ca6b660 user: dan tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to pages/btreemodule.in.

31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
..
69
70
71
72
73
74
75






76
77
78
79
80
81
82
...
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
...
904
905
906
907
908
909
910
911
912




















913
914
915
916
917
918
919
proc btree_api_defn {args} {
  eval header_api_defn btree.h $args
}
proc sqliteint_api_defn {args} {
  eval header_api_defn sqliteInt.h $args
}

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

  [h1 "Document Overview"]

  [h2 "Scope and Purpose"]

  <ul>
    <li><p> To make it easier to maintain, test and improve this critical
................................................................................
        [Tr] <td> H51**** <td> Requirement statements specifying the API provided by the B-Tree module.
        [Tr] <td> L****** <td> Requirement statements specifying some details of the internal workings of the B-Tree module.
      </table>

  [h2 "Glossary"]

    <table id=glossary>






      [Glossary "B-Tree Cursor" {
        <span class=todo>Define this.
      }]
      [Glossary "B-Tree Database Connection" {
        A B-Tree database connection is a single client connection to an in-memory 
        page cache, through which a single temporary or persistent database may
        be accessed. This term is used throughout this document to avoid confusing
................................................................................

       <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 table is either overfull or underfull.



     </ul>

    [h4 "Balance Deeper"]
      <ol>
................................................................................
	     entry associated with the overflow page.

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























  [h3 "Page Allocation and Deallocation"]

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







|







 







>
>
>
>
>
>







 







|







 







|

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







31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
..
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
...
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
...
910
911
912
913
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
939
940
941
942
943
944
945
proc btree_api_defn {args} {
  eval header_api_defn btree.h $args
}
proc sqliteint_api_defn {args} {
  eval header_api_defn sqliteInt.h $args
}

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
................................................................................
        [Tr] <td> H51**** <td> Requirement statements specifying the API provided by the B-Tree module.
        [Tr] <td> L****** <td> Requirement statements specifying some details of the internal workings of the B-Tree module.
      </table>

  [h2 "Glossary"]

    <table id=glossary>
      [Glossary "Balance-Siblings Algorithm" {
        The balance-siblings algorithm is one of four algorithms that may be used
	used to redistribute data within a b-tree structure after an insert or
        delete operation that causes a b-tree node to become overfull or underfull.
        See section <cite>balance_siblings</cite> for details.
      }]
      [Glossary "B-Tree Cursor" {
        <span class=todo>Define this.
      }]
      [Glossary "B-Tree Database Connection" {
        A B-Tree database connection is a single client connection to an in-memory 
        page cache, through which a single temporary or persistent database may
        be accessed. This term is used throughout this document to avoid confusing
................................................................................

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



     </ul>

    [h4 "Balance Deeper"]
      <ol>
................................................................................
	     entry associated with the overflow page.

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

      <ol>
        <li> Find the set of sibling pages to balance.
	<li> Find the set of cells involved in the balance. This is the set of
	     cells on the sibling pages, plus the "divider" cells if the
             sibling pages are not leaves of a table (intkey) b-tree.
        <li> Determine the new number of sibling pages and the new distribution 
             of cells. This is in itself a two-step process:
        <ol type="a">
          <li> Pack all cells...
          <li> Loop through the set of leaf pages...
        </ol>
        <li> Determine the set of database pages to use as the new sibling pages.
        <li> Populate each new sibling page.
        <li> Populate the parent page.
        <li> Populate pointer map entries associated with any cells that have moved.
	<li> Populate pointer map entries associated with the sibling pages,
             and any overflow pages pointed to by the new divider cells.
      </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.

Added req/llr50000.txt.























>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
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 

Changes to wrap.tcl.

470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
#
proc hd_read_requirement_file {filename varname} {
  global hd_req_rdr
  hd_reset_requirement_reader
  set in [open $filename]
  while {![eof $in]} {
    set line [gets $in]
    if {[regexp {^(HLR|UNDEF|SYSREQ) +([HSU]\d+) *(.*)} $line all type rn df]} {
      hd_add_one_requirement $varname
      set hd_req_rdr(rn) $rn
      set hd_req_rdr(derived) $df
    } elseif {[string trim $line]==""} {
      if {$hd_req_rdr(body)==""} {
        set hd_req_rdr(body) $hd_req_rdr(comment)
        set hd_req_rdr(comment) {}







|







470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
#
proc hd_read_requirement_file {filename varname} {
  global hd_req_rdr
  hd_reset_requirement_reader
  set in [open $filename]
  while {![eof $in]} {
    set line [gets $in]
    if {[regexp {^(HLR|UNDEF|SYSREQ) +([LHSU]\d+) *(.*)} $line all type rn df]} {
      hd_add_one_requirement $varname
      set hd_req_rdr(rn) $rn
      set hd_req_rdr(derived) $df
    } elseif {[string trim $line]==""} {
      if {$hd_req_rdr(body)==""} {
        set hd_req_rdr(body) $hd_req_rdr(comment)
        set hd_req_rdr(comment) {}