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