Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Fix a bug in the BTree balancing routine. (CVS 1387) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
6c73544bfacb891aae8d6124a2903ccf |
User & Date: | drh 2004-05-16 16:24:37.000 |
Context
2004-05-16
| ||
22:55 | Fix a bug meant real numbers with a negative sign were being stored as strings by default (instead of IEEE floats). (CVS 1388) (check-in: 9321e74263 user: danielk1977 tags: trunk) | |
16:24 | Fix a bug in the BTree balancing routine. (CVS 1387) (check-in: 6c73544bfa user: drh tags: trunk) | |
11:57 | Fix two bugs that were causing lots of tests to fail. (CVS 1386) (check-in: 5cba8a510c 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.141 2004/05/16 16:24:37 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. |
︙ | ︙ | |||
2808 2809 2810 2811 2812 2813 2814 | /* ** Return without doing any work if pPage is neither overfull nor ** underfull. */ assert( pPage->isInit ); assert( sqlite3pager_iswriteable(pPage->aData) ); pBt = pPage->pBt; | | > | 2808 2809 2810 2811 2812 2813 2814 2815 2816 2817 2818 2819 2820 2821 2822 2823 | /* ** Return without doing any work if pPage is neither overfull nor ** underfull. */ assert( pPage->isInit ); assert( sqlite3pager_iswriteable(pPage->aData) ); pBt = pPage->pBt; if( !pPage->isOverfull && pPage->nFree<pBt->usableSize*2/3 && pPage->nCell>=2){ relinkCellList(pPage); return SQLITE_OK; } /* ** Find the parent of the page to be balanced. If there is no parent, ** it means this page is the root page and special rules apply. |
︙ | ︙ | |||
3000 3001 3002 3003 3004 3005 3006 | ** Load pointers to all cells on sibling pages and the divider cells ** into the local apCell[] array. Make copies of the divider cells ** into space obtained form aSpace[] and remove the the divider Cells ** from pParent. ** ** If the siblings are on leaf pages, then the child pointers of the ** divider cells are stripped from the cells before they are copied | | > > > > > > > > | 3001 3002 3003 3004 3005 3006 3007 3008 3009 3010 3011 3012 3013 3014 3015 3016 3017 3018 3019 3020 3021 3022 3023 3024 3025 3026 3027 3028 3029 3030 3031 3032 3033 3034 3035 3036 3037 3038 3039 3040 | ** Load pointers to all cells on sibling pages and the divider cells ** into the local apCell[] array. Make copies of the divider cells ** into space obtained form aSpace[] and remove the the divider Cells ** from pParent. ** ** If the siblings are on leaf pages, then the child pointers of the ** divider cells are stripped from the cells before they are copied ** into aSpace[]. In this way, all cells in apCell[] are without ** child pointers. If siblings are not leaves, then all cell in ** apCell[] include child pointers. Either way, all cells in apCell[] ** are alike. ** ** leafCorrection: 4 if pPage is a leaf. 0 if pPage is not a leaf. ** leafData: 1 if pPage holds key+data and pParent holds only keys. */ nCell = 0; leafCorrection = pPage->leaf*4; leafData = pPage->leafData && pPage->leaf; for(i=0; i<nOld; i++){ MemPage *pOld = apCopy[i]; for(j=0; j<pOld->nCell; j++){ apCell[nCell] = pOld->aCell[j]; szCell[nCell] = cellSize(pOld, apCell[nCell]); nCell++; } if( i<nOld-1 ){ int sz = cellSize(pParent, apDiv[i]); if( leafData ){ /* With the LEAFDATA flag, pParent cells hold only INTKEYs that ** are duplicates of keys on the child pages. We need to remove ** the divider cells from pParent, but the dividers cells are not ** added to apCell[] because they are duplicates of child cells. */ dropCell(pParent, nxDiv, sz); }else{ u8 *pTemp; szCell[nCell] = sz; pTemp = &aSpace[iSpace]; iSpace += sz; assert( iSpace<=sizeof(aSpace) ); |
︙ | ︙ | |||
3050 3051 3052 3053 3054 3055 3056 | /* ** Figure out the number of pages needed to hold all nCell cells. ** Store this number in "k". Also compute szNew[] which is the total ** size of all cells on the i-th page and cntNew[] which is the index ** in apCell[] of the cell that divides page i from page i+1. ** cntNew[k] should equal nCell. ** | | | > > > > > > > > > > > > > > > > > > > > > | | > > > > | | < > > > | 3059 3060 3061 3062 3063 3064 3065 3066 3067 3068 3069 3070 3071 3072 3073 3074 3075 3076 3077 3078 3079 3080 3081 3082 3083 3084 3085 3086 3087 3088 3089 3090 3091 3092 3093 3094 3095 3096 3097 3098 3099 3100 3101 3102 3103 3104 3105 3106 3107 3108 3109 3110 3111 3112 3113 3114 3115 3116 3117 3118 3119 3120 3121 3122 3123 | /* ** Figure out the number of pages needed to hold all nCell cells. ** Store this number in "k". Also compute szNew[] which is the total ** size of all cells on the i-th page and cntNew[] which is the index ** in apCell[] of the cell that divides page i from page i+1. ** cntNew[k] should equal nCell. ** ** Values computed by this block: ** ** k: The total number of sibling pages ** szNew[i]: Spaced used on the i-th sibling page. ** cntNew[i]: Index in apCell[] and szCell[] for the first cell to ** the right of the i-th sibling page. ** usableSpace: Number of bytes of space available on each sibling. ** */ usableSpace = pBt->usableSize - 10 + leafCorrection; for(subtotal=k=i=0; i<nCell; i++){ subtotal += szCell[i]; if( subtotal > usableSpace ){ szNew[k] = subtotal - szCell[i]; cntNew[k] = i; if( leafData ){ i--; } subtotal = 0; k++; } } szNew[k] = subtotal; cntNew[k] = nCell; k++; /* ** The packing computed by the previous block is biased toward the siblings ** on the left side. The left siblings are always nearly full, while the ** right-most sibling might be nearly empty. This block of code attempts ** to adjust the packing of siblings to get a better balance. ** ** This adjustment is more than an optimization. The packing above might ** be so out of balance as to be illegal. For example, the right-most ** sibling might be completely empty. This adjustment is not optional. */ for(i=k-1; i>0; i--){ int szRight = szNew[i]; /* Size of sibling on the right */ int szLeft = szNew[i-1]; /* Size of sibling on the left */ int r; /* Index of right-most cell in left sibling */ int d; /* Index of first cell to the left of right sibling */ r = cntNew[i-1] - 1; d = r + 1 - leafData; while( szRight==0 || szRight+szCell[d]<=szLeft-szCell[r] ){ szRight += szCell[d]; szLeft -= szCell[r]; cntNew[i-1]--; r = cntNew[i-1] - 1; d = r + 1 - leafData; } szNew[i] = szRight; szNew[i-1] = szLeft; } assert( cntNew[0]>0 ); /* ** Allocate k new pages. Reuse old pages where possible. */ assert( pPage->pgno>1 ); |
︙ | ︙ |