/ Check-in [03d20673]
Login

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

Overview
Comment:Another optimization to the btree logic. (CVS 811)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:03d20673616cae0dca524fd04557798a98fb7069
User & Date: drh 2003-01-04 18:53:28
Context
2003-01-04
19:44
Parameterize the number of adjacent pages that participate in the balancing algorithm in the BTree. But leave the setting at the current value of 3. (CVS 812) check-in: 6c304024 user: drh tags: trunk
18:53
Another optimization to the btree logic. (CVS 811) check-in: 03d20673 user: drh tags: trunk
16:48
Optimizations to the BTree module for a modest speed improvement. (CVS 810) check-in: 39902a70 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/btree.c.

     5      5   ** a legal notice, here is a blessing:
     6      6   **
     7      7   **    May you do good and not evil.
     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12         -** $Id: btree.c,v 1.77 2003/01/04 16:48:09 drh Exp $
           12  +** $Id: btree.c,v 1.78 2003/01/04 18:53:28 drh Exp $
    13     13   **
    14     14   ** This file implements a external (disk-based) database using BTrees.
    15     15   ** For a detailed discussion of BTrees, refer to
    16     16   **
    17     17   **     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
    18     18   **     "Sorting And Searching", pages 473-480. Addison-Wesley
    19     19   **     Publishing Company, Reading, Massachusetts.
................................................................................
  2119   2119     int rc;                      /* The return code */
  2120   2120     int iCur;                    /* apCell[iCur] is the cell of the cursor */
  2121   2121     MemPage *pOldCurPage;        /* The cursor originally points to this page */
  2122   2122     int subtotal;                /* Subtotal of bytes in cells on one page */
  2123   2123     int cntNew[4];               /* Index in apCell[] of cell after i-th page */
  2124   2124     int szNew[4];                /* Combined size of cells place on i-th page */
  2125   2125     MemPage *extraUnref = 0;     /* A page that needs to be unref-ed */
  2126         -  Pgno pgno, swabPgno;         /* Page number */
  2127   2126     Cell *apCell[MX_CELL*3+5];   /* All cells from pages being balanceed */
  2128   2127     int szCell[MX_CELL*3+5];     /* Local size of all cells */
  2129   2128     Cell aTemp[2];               /* Temporary holding area for apDiv[] */
  2130   2129     MemPage aOld[3];             /* Temporary copies of pPage and its siblings */
  2131   2130   
  2132   2131     /* 
  2133   2132     ** Return without doing any work if pPage is neither overfull nor
................................................................................
  2194   2193       rc = sqlitepager_write(pPage);
  2195   2194       if( rc ) return rc;
  2196   2195       rc = allocatePage(pBt, &pChild, &pgnoChild, sqlitepager_pagenumber(pPage));
  2197   2196       if( rc ) return rc;
  2198   2197       assert( sqlitepager_iswriteable(pChild) );
  2199   2198       copyPage(pChild, pPage);
  2200   2199       pChild->pParent = pPage;
  2201         -    pChild->idxParent = pChild->nCell;
         2200  +    pChild->idxParent = 0;
  2202   2201       sqlitepager_ref(pPage);
  2203   2202       pChild->isOverfull = 1;
  2204   2203       if( pCur && pCur->pPage==pPage ){
  2205   2204         sqlitepager_unref(pPage);
  2206   2205         pCur->pPage = pChild;
  2207   2206       }else{
  2208   2207         extraUnref = pChild;
................................................................................
  2217   2216     assert( pParent->isInit );
  2218   2217     
  2219   2218     /*
  2220   2219     ** Find the Cell in the parent page whose h.leftChild points back
  2221   2220     ** to pPage.  The "idx" variable is the index of that cell.  If pPage
  2222   2221     ** is the rightmost child of pParent then set idx to pParent->nCell 
  2223   2222     */
  2224         -  idx = -1;
  2225         -  pgno = sqlitepager_pagenumber(pPage);
  2226         -  swabPgno = SWAB32(pBt, pgno);
  2227         -  for(i=0; i<pParent->nCell; i++){
  2228         -    if( pParent->apCell[i]->h.leftChild==swabPgno ){
  2229         -      idx = i;
  2230         -      break;
         2223  +  if( pParent->idxShift ){
         2224  +    Pgno pgno, swabPgno;
         2225  +    pgno = sqlitepager_pagenumber(pPage);
         2226  +    swabPgno = SWAB32(pBt, pgno);
         2227  +    for(idx=0; idx<pParent->nCell; idx++){
         2228  +      if( pParent->apCell[idx]->h.leftChild==swabPgno ){
         2229  +        break;
         2230  +      }
  2231   2231       }
         2232  +    assert( idx<pParent->nCell || pParent->u.hdr.rightChild==swabPgno );
         2233  +  }else{
         2234  +    idx = pPage->idxParent;
  2232   2235     }
  2233         -  if( idx<0 && pParent->u.hdr.rightChild==swabPgno ){
  2234         -    idx = pParent->nCell;
  2235         -  }
  2236         -  assert( idx>=0 );
  2237         -  /* assert( pParent->idxShift || idx==pPage->idxParent ); */
  2238   2236   
  2239   2237     /*
  2240   2238     ** Initialize variables so that it will be safe to jump
  2241   2239     ** directly to balance_cleanup at any moment.
  2242   2240     */
  2243   2241     nOld = nNew = 0;
  2244   2242     sqlitepager_ref(pParent);