SQLite

Check-in [64a75c4cd4]
Login

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

Overview
Comment:Fix a problem with B+trees. (CVS 1366)
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 64a75c4cd40f79c7b384bb2972922ff0c10212a4
User & Date: drh 2004-05-12 21:11:27.000
Context
2004-05-13
01:12
Allocate more overflow data onto overflow pages, thus wasting less disk space. (CVS 1367) (check-in: 1d52a4bb47 user: drh tags: trunk)
2004-05-12
21:11
Fix a problem with B+trees. (CVS 1366) (check-in: 64a75c4cd4 user: drh tags: trunk)
19:18
Implement a B+tree option (all data stored on leaves). (CVS 1365) (check-in: b8f70d17f0 user: drh tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/btree.c. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/*
** 2004 April 6
**
** The author disclaims copyright to this source code.  In place of
** 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.












|








1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/*
** 2004 April 6
**
** The author disclaims copyright to this source code.  In place of
** 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.
︙︙
1983
1984
1985
1986
1987
1988
1989


1990
1991
1992
1993
1994
1995
1996

        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;
        }
      }








>
>








1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998

        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

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








|








9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#
#***********************************************************************
# 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.
︙︙
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

    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








|
|












108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

    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