主要分析balance_nonroot()函數里的代碼

1.iParentIdx和nxDiv的作用

iParentIdx的來源是

iIdx = pCur->aiIdx[iPage-1];

在btree中查找葉子結點是從根結點開始一層層往下，iParentIdx就是查找到當前結點時，父結點對應第幾個cell

當孩子結點分裂成2半時，需要把一個cell移到父結點，這個cell對應的偏移地址由nxDiv決定，對應的代碼如下

int nxDiv; /* Next divider slot in pParent->aCell[] */i = pParent->nOverflow + pParent->nCell;if( i<2 ){nxDiv = 0;}else{if( iParentIdx==0 ){ nxDiv = 0;}else if( iParentIdx==i ){nxDiv = i-2;}else{nxDiv = iParentIdx-1;}i = 2;}if( (i+nxDiv-pParent->nOverflow)==pParent->nCell ){pRight = &pParent->aData[pParent->hdrOffset+8];}else{pRight = findCell(pParent, i+nxDiv-pParent->nOverflow);}

當cell的數量很少時或者子結點是父結點第0個cell的孩子時nxDiv = 0，當滿足i<2 或iParentIdx==i條件時可以推出當前父結點的偏移在最右邊即(i+nxDiv-pParent->nOverflow)==pParent->nCell，所以新的孩子頁號記錄在最右邊（pRight = &pParent->aData[pParent->hdrOffset+8];），回顧頁面頭的結構可以知道開始第8個字節代表最右孩子頁號。如果不滿足這個條件，找出分裂點的cell偏移（nxDiv = iParentIdx-1;），新的孩子頁號會記錄在這里。

2. nMaxCells

關鍵代碼

int nMaxCells = 0; /* Allocated size of apCell, szCell, aFrom. */nMaxCells = nOld*(MX_CELL(pBt) + ArraySize(pParent->apOvfl));nMaxCells = (nMaxCells + 3)&~3;/*** Allocate space for memory structures*/szScratch =nMaxCells*sizeof(u8*) /* b.apCell */+ nMaxCells*sizeof(u16) /* b.szCell */+ pBt->pageSize; /* aSpace1

要注意這里nMaxCells只是分配空間用的，并沒有在哪里用做條件判斷，再來看一下MX_CELL的代碼

/* The maximum number of cells on a single page of the database. This ** assumes a minimum cell size of 6 bytes (4 bytes for the cell itself ** plus 2 bytes for the index to the cell in the page header). Such ** small cells will be rare, but they are possible. */ #define MX_CELL(pBt) ((pBt->pageSize-8)/6)

這里把一個cell的長度當作4字節來看待，如果仔細去對照cell的格式的話會非常難理解，因為cell里有些字段是變長的，但如果把這4字節看成一個平均估算值就好理解了，這個maximum number of cells是自己規定的，不受什么制約，多一點少一點都沒關系。

3.apOld的作用是什么

該變量定義如下

MemPage *apOld[NB]; /* pPage and up to two siblings */

還有NN和NB的定義如下

#define NN 1 /* Number of neighbors on either side of pPage */ #define NB 3 /* (NN*2+1): Total pages involved in the balance */

為什么NN是1而NB是3，分別有什么含義？

按照我個人的理解，一個中間結點各有左右兄弟結點一個，在最左邊或最右邊時另說，所以NN肯定時1，NB就是2個兄弟子結點再加一個父結點，當NN>1時會不會處理多個鄰居結點呢？NB=3意味著apOld分別存儲父結點、左右孩子結點的數據頁，代碼如下

pgno = get4byte(pRight);while( 1 ){rc = getAndInitPage(pBt, pgno, &apOld[i], 0, 0);....if( (i--)==0 ) break;if( pParent->nOverflow && i+nxDiv==pParent->aiOvfl[0] ){apDiv[i] = pParent->apOvfl[0];pgno = get4byte(apDiv[i]);szNew[i] = pParent->xCellSize(pParent, apDiv[i]);pParent->nOverflow = 0;}else{apDiv[i] = findCell(pParent, i+nxDiv-pParent->nOverflow);pgno = get4byte(apDiv[i]);szNew[i] = pParent->xCellSize(pParent, apDiv[i]);......

這段代碼執行之后apOld的分布如下

4.b.apCell的作用

主要是把apOld所在頁的cell緩存起來，確切的說應該是存放cell的2字節索引

for(i=0; i<nOld; i++){MemPage *pOld = apOld[i];memset(&b.szCell[b.nCell], 0, sizeof(b.szCell[0])*(limit+pOld->nOverflow));if( pOld->nOverflow>0 ){//先緩存比溢出cell key值小的limit = pOld->aiOvfl[0]; for(j=0; j<limit; j++){b.apCell[b.nCell] = aData + (maskPage & get2byteAligned(piCell));piCell += 2;b.nCell++;}//再緩存溢出cellfor(k=0; k<pOld->nOverflow; k++){assert( k==0 || pOld->aiOvfl[k-1]+1==pOld->aiOvfl[k] );/* NOTE 1 */b.apCell[b.nCell] = pOld->apOvfl[k];b.nCell++;}}//最后緩存比溢出cell key值大的piEnd = aData + pOld->cellOffset + 2*pOld->nCell;while( piCell<piEnd ){assert( b.nCell<nMaxCells );b.apCell[b.nCell] = aData + (maskPage & get2byteAligned(piCell));piCell += 2;b.nCell++;}}

那么b.apCell的空間容量夠存3個頁的cell嗎，答案是夠的，看下面代碼就可以明白

/* Make nMaxCells a multiple of 4 in order to preserve 8-byte** alignment */nMaxCells = nOld*(MX_CELL(pBt) + ArraySize(pParent->apOvfl));nMaxCells = (nMaxCells + 3)&~3;/*** Allocate space for memory structures*/szScratch =nMaxCells*sizeof(u8*) /* b.apCell */+ nMaxCells*sizeof(u16) /* b.szCell */+ pBt->pageSize; /* aSpace1 */

nMaxCells的值是已經乘以一個nOld的一個系數了。

5.放棄。。。

放棄的原因是代碼寫的太雜了，考慮的情況太多，全部都擠在了一起，反而抓不住b-tree的重心在哪里，里面這么多變量理解起來很費勁，還有一大堆英文注釋看不懂，主要是不知道代碼的設計場景，所以很難建立一個直觀的感受。

總結

以上是生活随笔為你收集整理的SQLite源码学习(40) balance初步分析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。