Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Add a few interface requirements to btreemodule.html. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
9949936e6eb09e235887463cd6181ef9 |
User & Date: | dan 2009-06-09 11:58:37.000 |
Context
2009-06-11
| ||
03:44 | Add a diagram for delete operations. (check-in: dbcfaf4922 user: dan tags: trunk) | |
2009-06-09
| ||
11:58 | Add a few interface requirements to btreemodule.html. (check-in: 9949936e6e user: dan 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.
︙ | ︙ | |||
37 38 39 40 41 42 43 44 45 46 47 48 49 50 | 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 sub-system of the SQLite software library. <li><p> To facilitate development of compatible backend modules that can be used with other SQLite sub-systems, either for experimental or production purposes. | > > > > > > | 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | fancyformat_document "SQLite B-Tree Module" {hlr50000.txt llr50000.txt} { [h1 "Document Overview"] [h2 "Scope and Purpose"] <p> This document provides a description of the functionality of and public interface offered by the SQLite b-tree module. It also, to a certain extent, describes the algorithm and implementation techniques used internally by the module. <ul> <li><p> To make it easier to maintain, test and improve this critical sub-system of the SQLite software library. <li><p> To facilitate development of compatible backend modules that can be used with other SQLite sub-systems, either for experimental or production purposes. |
︙ | ︙ | |||
731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 | sqlite3BtreePrevious sqlite3BtreeEof] [btree_api_defn sqlite3BtreeKeySize sqlite3BtreeKey sqlite3BtreeKeyFetch \ sqlite3BtreeDataFetch sqlite3BtreeDataSize sqlite3BtreeData] [btree_api_defn sqlite3BtreeCount] [btree_api_defn sqlite3BtreeMovetoUnpacked] <p class=todo> Not clear how to deal with these. Define an external module to encapsulate these and define sorting order etc.? That's tricky as things are because the UnpackedRecord.flags field defines the "search mode" used by sqlite3BtreeMovetoUnpacked. | > > > > > > > > > > > > > > > | 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 | sqlite3BtreePrevious sqlite3BtreeEof] [btree_api_defn sqlite3BtreeKeySize sqlite3BtreeKey sqlite3BtreeKeyFetch \ sqlite3BtreeDataFetch sqlite3BtreeDataSize sqlite3BtreeData] [btree_api_defn sqlite3BtreeCount] [h3 sqlite3BtreeMovetoUnpacked] <p> The sqlite3BtreeMovetoUnpacked function is used to [btree_api_defn sqlite3BtreeMovetoUnpacked] <p> The following requirements specify exactly how a b-tree cursor is to be moved by a successful call to sqlite3BtreeMovetoUnpacked. [fancyformat_import_requirement L50008] [fancyformat_import_requirement L50009] [fancyformat_import_requirement L50010] [fancyformat_import_requirement L50011] <p class=todo> Not clear how to deal with these. Define an external module to encapsulate these and define sorting order etc.? That's tricky as things are because the UnpackedRecord.flags field defines the "search mode" used by sqlite3BtreeMovetoUnpacked. |
︙ | ︙ | |||
769 770 771 772 773 774 775 | [btree_api_defn sqlite3BtreeCreateTable] [btree_api_defn BTREE_INTKEY BTREE_ZERODATA BTREE_LEAFDATA] [btree_api_defn sqlite3BtreeDropTable sqlite3BtreeClearTable sqlite3BtreeUpdateMeta] | | > > > > | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 | [btree_api_defn sqlite3BtreeCreateTable] [btree_api_defn BTREE_INTKEY BTREE_ZERODATA BTREE_LEAFDATA] [btree_api_defn sqlite3BtreeDropTable sqlite3BtreeClearTable sqlite3BtreeUpdateMeta] [btree_api_defn sqlite3BtreeDelete] [btree_api_defn sqlite3BtreeCursorHasMoved sqlite3BtreePutData] [btree_api_defn sqlite3BtreeIncrVacuum] [h3 sqlite3BtreeInsert] [btree_api_defn sqlite3BtreeInsert] [fancyformat_import_requirement L50001] <p class=todo> Or, if an entry with the specified key exists, it shall be replaced. <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". <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 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 information used by sqlite3BtreeInsert to optimize the insert operation. They may be safely ignored by alternative b-tree implementations. <p class=todo> There should be some rationalization for these, eventually. Some tracebility from somewhere to show how the b-tree module offering these slightly esoteric interfaces is helpful to SQLite overall. [fancyformat_import_requirement L50005] [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. [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. |
︙ | ︙ | |||
826 827 828 829 830 831 832 | <li> sqlite3PagerBackupPtr </ul> </ul> [h1 "Module Implementation"] | | > > | < | | > > > > | | < > | 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 | <li> sqlite3PagerBackupPtr </ul> </ul> [h1 "Module Implementation"] [h2 "Database Image Traversal"] [h2 "Database Image Manipulation"] <p class=todo> 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 "B-Tree Insert/Replace Entry"] [h3 "B-Tree Delete Entry"] [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 |
︙ | ︙ | |||
879 880 881 882 883 884 885 | </ol> [Figure btreemodule_balance_deeper.svg figure_balance_deeper "Example Balance Deeper Transform"] [h4 "Balance Shallower"] <ol> | | | 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 | </ol> [Figure btreemodule_balance_deeper.svg figure_balance_deeper "Example Balance Deeper Transform"] [h4 "Balance Shallower"] <ol> <li> Copy node 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"] |
︙ | ︙ | |||
912 913 914 915 916 917 918 | <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] | | | 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 | <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 L51001] <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! |
︙ | ︙ | |||
1068 1069 1070 1071 1072 1073 1074 | 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> | | > > | 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 | 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. [h2 "Transactions and Savepoints"] <p class=todo> Requirements surrounding how transactions are made atomic and isolated. Also how savepoints are implemented. What happens to active cursors after |
︙ | ︙ |
Changes to pages/fancyformat.tcl.
︙ | ︙ | |||
146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 | } proc fancyformat_import_requirement {reqid} { lappend ::Requirements $reqid set ret "<p class=req id=$reqid><span>[lindex $::ffreq($reqid) 1]</span>" if {[llength [lindex $::ffreq($reqid) 0]]} { append ret " (P: [lindex $::ffreq($reqid) 0])" } append ret "</p>" } set ::Requirements [list] proc fancyformat_document {zTitle lReqfile zBody} { unset -nocomplain ::ffreq foreach f $lReqfile { hd_read_requirement_file $::DOC/req/$f ::ffreq } set body [subst -novariables $zBody] hd_puts [subst { <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"> <html> <head> <link type="text/css" rel="stylesheet" href="images/fileformat/rtdocs.css"> </head> | > > > > > > > > > > > | 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 | } proc fancyformat_import_requirement {reqid} { lappend ::Requirements $reqid set ret "<p class=req id=$reqid><span>[lindex $::ffreq($reqid) 1]</span>" if {[llength [lindex $::ffreq($reqid) 0]]} { append ret " (P: [lindex $::ffreq($reqid) 0])" } if {[info exists ::ffreq_children($reqid)]} { append ret " (C: $::ffreq_children($reqid))" } append ret "</p>" } set ::Requirements [list] proc fancyformat_document {zTitle lReqfile zBody} { unset -nocomplain ::ffreq unset -nocomplain ::ffreq_children foreach f $lReqfile { hd_read_requirement_file $::DOC/req/$f ::ffreq } foreach req [array names ::ffreq] { foreach parent [lindex $::ffreq($req) 0] { lappend ::ffreq_children($parent) $req } } set body [subst -novariables $zBody] hd_puts [subst { <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"> <html> <head> <link type="text/css" rel="stylesheet" href="images/fileformat/rtdocs.css"> </head> |
︙ | ︙ |
Changes to req/llr50000.txt.
|
| > > > > > > > > > > > > > > > > > > > > > > > > > > > | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > < < < < | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 | 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 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. HLR L50003 H50128 If the b-tree cursor passed to sqlite3BtreeInsert as the first argument is open on a table b-tree, then the database record associated with the new entry shall consist of a copy of the first nData bytes of the buffer pointed to by pData followed by nZero zero (0x00) bytes, where pData, nData and nZero are the fourth, fifth and sixth parameters passed to sqlite3BtreeInsert, respectively. HLR L50004 H50128 If the b-tree cursor passed to sqlite3BtreeInsert as the first argument is open on an index b-tree, then the values passed as the fourth, fifth and sixth parameters shall be ignored. The key (a database record) used by the new entry shall consist of the first nKey bytes of the buffer pointed to by pKey, where pKey and nKey are the second and third parameters passed to sqlite3BtreeInsert, respectively. HLR L50005 If the value passed as the seventh parameter to a call to sqlite3BtreeInsert is non-zero, sqlite3BtreeInsert shall interpret this to mean that it is likely (but not certain) that the key belonging to the new entry is larger than the largest key currently stored in the b-tree structure, and optimize accordingly. HLR L50006 If the value passed as the eighth parameter to a call to sqlite3BtreeInsert is non-zero, then the B-Tree module shall interpret this to mean that the the b-tree cursor has already been positioned by a successful call to sqlite3BtreeMovetoUnpacked specifying the same key value as is being inserted, and that sqlite3BtreeMovetoUnpacked has set the output value required by L50011 to this value. HLR L50008 If a call is made to sqlite3BtreeMovetoUnpacked specifying a key value for which there exists an entry with a matching key value in the b-tree structure, the b-tree cursor shall be moved to point to this entry. In this case *pRes (the value of the "int" variable pointed to by the pointer passed as the fifth parameter to sqlite3BtreeMovetoUnpacked) shall be set to 0 before returning. HLR L50009 If a call is made to sqlite3BtreeMovetoUnpacked specifying a key value for which there does not exist an entry with a matching key value in the b-tree structure, the b-tree cursor shall be moved to point to an entry located on the leaf page that would contain the requested entry, were it present. HLR L50010 If the condition specified in L50009 is met and the b-tree structure contains one or more entries (is not empty), the b-tree cursor shall be left pointing to an entry that would lie adjacent (immediately before or after in order by key) to the requested entry on the leaf page, were it present. HLR L50011 If the condition specified in L50009 is met and the b-tree cursor is left pointing to an entry with a smaller key than that requested, or the cursor 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 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. |