Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Fix a problem with B+trees. (CVS 1366) |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | trunk |
| Files: | files | file ages | folders |
| SHA1: |
64a75c4cd40f79c7b384bb2972922ff0 |
| User & Date: | drh 2004-05-12 21:11:27 |
Context
|
2004-05-13
| ||
| 01:12 | Allocate more overflow data onto overflow pages, thus wasting less disk space. (CVS 1367) check-in: 1d52a4bb user: drh tags: trunk | |
|
2004-05-12
| ||
| 21:11 | Fix a problem with B+trees. (CVS 1366) check-in: 64a75c4c user: drh tags: trunk | |
| 19:18 | Implement a B+tree option (all data stored on leaves). (CVS 1365) check-in: b8f70d17 user: drh tags: trunk | |
Changes
Changes to src/btree.c.
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
....
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
|
** a legal notice, here is a blessing: ** ** May you do good and not evil. ** May you find forgiveness for yourself and forgive others. ** May you share freely, never taking more than you give. ** ************************************************************************* ** $Id: btree.c,v 1.129 2004/05/12 19:18:16 drh Exp $ ** ** This file implements a external (disk-based) database using BTrees. ** For a detailed discussion of BTrees, refer to ** ** Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3: ** "Sorting And Searching", pages 473-480. Addison-Wesley ** Publishing Company, Reading, Massachusetts. ................................................................................ rc = sqlite3BtreeKey(pCur, 0, nCellKey, pCellKey); c = pCur->xCompare(pCur->pArg, nCellKey, pCellKey, nKey, pKey); sqliteFree(pCellKey); if( rc ) return rc; } if( c==0 ){ if( pPage->leafData && !pPage->leaf ){ break; }else{ pCur->iMatch = c; if( pRes ) *pRes = 0; return SQLITE_OK; } } |
|
>
>
|
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
....
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
|
** a legal notice, here is a blessing: ** ** May you do good and not evil. ** May you find forgiveness for yourself and forgive others. ** May you share freely, never taking more than you give. ** ************************************************************************* ** $Id: btree.c,v 1.130 2004/05/12 21:11:27 drh Exp $ ** ** This file implements a external (disk-based) database using BTrees. ** For a detailed discussion of BTrees, refer to ** ** Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3: ** "Sorting And Searching", pages 473-480. Addison-Wesley ** Publishing Company, Reading, Massachusetts. ................................................................................ rc = sqlite3BtreeKey(pCur, 0, nCellKey, pCellKey); c = pCur->xCompare(pCur->pArg, nCellKey, pCellKey, nKey, pKey); sqliteFree(pCellKey); if( rc ) return rc; } if( c==0 ){ if( pPage->leafData && !pPage->leaf ){ lwr = pCur->idx; upr = lwr - 1; break; }else{ pCur->iMatch = c; if( pRes ) *pRes = 0; return SQLITE_OK; } } |
Changes to test/btree6.test.
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
...
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
# #*********************************************************************** # This file implements regression tests for SQLite library. The # focus of this script is btree database backend - specifically # the B+tree tables. B+trees store all data on the leaves rather # that storing data with keys on interior nodes. # # $Id: btree6.test,v 1.1 2004/05/12 19:18:17 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl # Insert many entries into the table that cursor $cur points to. ................................................................................ incr cnt 200 check_table $cur $cnt } {} do_test btree6-1.$i.2 { btree_integrity_check $b1 1 $tab } {} do_test btree6-1.$i.3 { random_deletes $cur 190 incr cnt -190 check_table $cur $cnt } {} do_test btree6-1.$i.4 { btree_integrity_check $b1 1 $tab } {} } btree_close_cursor $cur btree_commit $b1 finish_test |
|
|
|
|
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
...
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
# #*********************************************************************** # This file implements regression tests for SQLite library. The # focus of this script is btree database backend - specifically # the B+tree tables. B+trees store all data on the leaves rather # that storing data with keys on interior nodes. # # $Id: btree6.test,v 1.2 2004/05/12 21:11:27 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl # Insert many entries into the table that cursor $cur points to. ................................................................................ incr cnt 200 check_table $cur $cnt } {} do_test btree6-1.$i.2 { btree_integrity_check $b1 1 $tab } {} do_test btree6-1.$i.3 { random_deletes $cur 90 incr cnt -90 check_table $cur $cnt } {} do_test btree6-1.$i.4 { btree_integrity_check $b1 1 $tab } {} } btree_close_cursor $cur btree_commit $b1 finish_test |