static S_16 FAR PASCAL
SearchItemInPage(IDX_PAGE FAR *lpIdxPage, IDX_KEYS FAR *lpKey, U_32 u32KeyType)
{
S_16 s16Low;
S_16 s16High;
S_16 s16Mid;
/*
* ディスクアクセスに比べれば無視できるレベルだが、
* 一応高速化のためにバイナリサーチを使用する。
*
* キーとマッチしたら、マッチしたキーの添え字を、
* マッチしなかったら、一つ小さいキーの添え字を返す。
* 下のAのようなページがあって、キー0をサーチしたら、
* DummyITEMの添え字が返される。
* +-------+-------+-------+
* A | Dummy | 1 | 2 |
* +-------+-------+-------+
* ／ ｜ ＼
* ／ NIL ＼
* +-------+-------+-------+ +-------+-------+-------+
* B | Dummy | -1 | 0 | C | Dummy | 4 | 5 |
* +-------+-------+-------+ +-------+-------+-------+
* そしてそのDummyITEMは、1より小さい値の集まりであるBページに
* アクセスするために使用される。
*
* また、Aページでキー3をサーチすると、2のITEMの添え字が返る。
* この関数を呼び出した親の関数は、その添え字を
* 2より大きな値の集まりであるCページにアクセスするために使用する。
*
* このルーチンはコード部よりコメントの方が長い。許してください。
*/
s16Low = 1;
s16High = lpIdxPage->s16ItemUsed + (S_16)1;
while (s16Low < s16High) {
s16Mid = (s16Low + s16High) / (S_16)2;
if (IsamKeyComp(&lpIdxPage->item[s16Mid].keys,
lpKey, u32KeyType) <= 0) {
s16Low = s16Mid + (S_16)1;
} else {
s16High = s16Mid;
}
}
return --s16High;
}
else {
/*
* このページ内にあったが、
* しかしそいつは子を持っていて、
* サクサク削除するわけにはいかない。
* その前に子供達の世話が必要である
*
* +-----+-----+
* A| 7 | 8 |
* +-----+-----+
* ／ ＼
* +-----+-----+ +-----+-----+
* B| 3 | 4 | D| 9 | |
* +-----+-----+ +-----+-----+
* ＼
* +-----+-----+
* C| 5 | 6 |
* +-----+-----+
*
* 上のようなTreeで7を削除しようとした場合、
* この状態になる。
* その場合、下のようにする。
*
* +-----+-----+
* A| 6 | 8 |
* +-----+-----+
* ／ ＼
* +-----+-----+ +-----+-----+
* B| 3 | 4 | D| 9 | |
* +-----+-----+ +-----+-----+
* ＼
* +-----+-----+
* C| 5 | |
* +-----+-----+
*
* この動きを置き換えといい、
* これを行っているのがReplaceItem()である。
*/
nResult = ReplaceItem(lpFld, s32TruthPtr, lpfUnderFlow,
s32PagePtr, s16High, lps16StsCode);
if (*lpfUnderFlow != FALSE) {
/*
* 次のようなTreeを考えてみよう。（次数２）
*
* +----+----+----+----+
* A| 20 | 30 | 40 | |
* +----+----+----+----+
* ／ ＼
* +----+----+--+--+ +----+----+--+--+
* B| 25 | 27 | | | C| 34 | 36 | | |
* +----+----+--+--+ +----+----+--+--+
*
* 上のようなTreeで27を削除しようとした場合
* 下のようになる。
*
* +----+----+----+----+
* A| 20 | 30 | 40 | |
* +----+----+----+----+
* ／ ＼
* +----+----+--+--+ +----+----+--+--+
* B| 25 | | | | C| 34 | 36 | | |
* +----+----+--+--+ +----+----+--+--+
*
* ここで問題が発生する。BTreeの基本特性で
* 次数２(１ページの項目数は2*2=4)のBTreeは
* １ページ内の項目数は２より小さくならない
* したがって、ページBのITEM数が明らかに不
* 足している。この状態をアンダーフローと
* いう。
* Bが不足しているからといって単純にCページ
* から34を持ってくるわけにもいかない。それ
* は「30より左の子ページにあるITEMはすべて
* 30より小さくなければならない」という規則
* に反し、またCのページはアンダーフローを
* 再び引き起こす。
* この場合は30をAからBに引きずり下ろし、
* BとCを併合する。するとTreeは下のように
* なる。
* これを行っているのがUnderFlow()である。
*
* +----+----+----+----+
* A| 20 | 40 | | |
* +----+----+----+----+
* ／
* +----+----+----+----+
* B| 25 | 30 | 34 | 36 |
* +----+----+----+----+
*/
nResult = UnderFlow(lpFld, s32PagePtr,
lpfUnderFlow, s32TruthPtr,
s16High - (S_16)1, lps16StsCode);
ふう。(^^;コードが解決する問題が本質的に複雑な場合、こういったコメントが力を発揮します。
| コメントへ戻る | _ | Top of Site |