主要分析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初步分析的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。