/ Check-in [183c42ea]
Login

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

Overview
Comment:Add comments to the new balance_quick() routine. (CVS 2212)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 183c42eac82b41da7905e44a43913f04acc46ade
User & Date: drh 2005-01-14 22:55:49
Context
2005-01-15
00:36
Improved coverage for insert.c. (CVS 2213) check-in: 997d8aff user: drh tags: trunk
2005-01-14
22:55
Add comments to the new balance_quick() routine. (CVS 2212) check-in: 183c42ea user: drh tags: trunk
13:50
Experimental patch to balance() (use -DSQLITE_BALANCE_QUICK). (CVS 2211) check-in: c550d80c user: danielk1977 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.232 2005/01/14 13:50:12 danielk1977 Exp $
           12  +** $Id: btree.c,v 1.233 2005/01/14 22:55:49 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.
................................................................................
  3554   3554   */
  3555   3555   #define NN 1             /* Number of neighbors on either side of pPage */
  3556   3556   #define NB (NN*2+1)      /* Total pages involved in the balance */
  3557   3557   
  3558   3558   /* Forward reference */
  3559   3559   static int balance(MemPage*, int);
  3560   3560   
         3561  +/*
         3562  +** This version of balance() handles the common special case where
         3563  +** a new entry is being inserted on the extreme right-end of the
         3564  +** tree, in other words, when the new entry will become the largest
         3565  +** entry in the tree.
         3566  +**
         3567  +** Instead of trying balance the 3 right-most leaf pages, just add
         3568  +** a new page to the right-hand side and put the one new entry in
         3569  +** that page.  This leaves the right side of the tree somewhat
         3570  +** unbalanced.  But odds are that we will be inserting new entries
         3571  +** at the end soon afterwards so the nearly empty page will quickly
         3572  +** fill up.  On average.
         3573  +**
         3574  +** pPage is the leaf page which is the right-most page in the tree.
         3575  +** pParent is its parent.  pPage must have a single overflow entry
         3576  +** which is also the right-most entry on the page.
         3577  +*/
  3561   3578   static int balance_quick(MemPage *pPage, MemPage *pParent){
  3562   3579     int rc;
  3563   3580     MemPage *pNew;
  3564   3581     Pgno pgnoNew;
  3565   3582     u8 *pCell;
  3566   3583     int szCell;
  3567   3584     CellInfo info;
................................................................................
  3677   3694     pBt = pPage->pBt;
  3678   3695     pParent = pPage->pParent;
  3679   3696     sqlite3pager_write(pParent->aData);
  3680   3697     assert( pParent );
  3681   3698     TRACE(("BALANCE: begin page %d child of %d\n", pPage->pgno, pParent->pgno));
  3682   3699   
  3683   3700   #ifdef SQLITE_BALANCE_QUICK
         3701  +  /*
         3702  +  ** A special case:  If a new entry has just been inserted into a
         3703  +  ** table (that is, a btree with integer keys and all data at the leaves)
         3704  +  ** an the new entry is the right-most entry in the tree (it has the
         3705  +  ** largest key) then use the special balance_quick() routine for
         3706  +  ** balancing.  balance_quick() is much faster and results in a tighter
         3707  +  ** packing of data in the common case.
         3708  +  */
  3684   3709     if( pPage->leaf &&
  3685   3710         pPage->intKey &&
  3686   3711         pPage->leafData &&
  3687   3712         pPage->nOverflow==1 &&
  3688   3713         pPage->aOvfl[0].idx==pPage->nCell &&
  3689   3714         get4byte(&pParent->aData[pParent->hdrOffset+8])==pPage->pgno
  3690   3715     ){