-------------------------------------------------------------------------------- 标题: B-tree查找函数 作者: Kyee Ye 日期: 2011.04.17 --------------------------------------------------------------------------------
在 B-tree 中搜索键值，结点内可以使用二分查找，若要查找指定范围内数据与查找键值相比相对要复杂一点。
现给出查找指定范围内第一项和最后一项数据的示例代码：
// B-tree 的项 typedef struct { long Key; // 键值 void* Link; // 子结点或数据 } TBTItem, *PBTItem; // B-tree 的结点 typedef struct { Byte Count; // 项数[1..维数] bool IsLeaf; // 是否为叶子结点 TBTItem Items[100]; // 项列表(假设 B-tree 维度为 100) } TBTNode, *PBTNode; // 查找范围内的第一项并返回序号(注: AFrom < ATo) TBTNode* FindFirstItem(TBTNode* ARoot, long AFrom, long ATo, bool AIsInc, long& AIndex) { // 初始化 bool boolRet = false; TBTNode* pNode = ARoot; TBTNode* pNext = NULL; long intNext = 0; long intBegin, intEnd, intMid, intKey; // 循环查找层 while (pNode != NULL) { // 初始化(注: pNode->Count >= 1) intEnd = pNode->Count - 1; intBegin = 0; // 结点内二分查找 while (intBegin <= intEnd) { intMid = (intBegin + intEnd) >> 1; intKey = pNode->Items[intMid].Key; if (intKey < AFrom) intBegin = intMid + 1; else { intEnd = intMid - 1; if (intKey == AFrom) { intBegin = intMid; break; } } } // 判断是否为叶结点 AIndex = intBegin; if (pNode->IsLeaf) { if (intKey != AFrom) { if (AIndex != pNode->Count) { boolRet = (pNode->Items[AIndex].Key <= ATo); break; } } else if (AIsInc) { boolRet = true; break; } else if (AIndex < pNode->Count - 1) { AIndex++; boolRet = (pNode->Items[AIndex].Key <= ATo); break; } // 下一结点项 if (pNext == NULL) break; else { pNode = (TBTNode*)pNext->Item[intNext].Link; pNext = NULL; } } else { // 校正索引 if (AIndex == pNode->Count) AIndex = pNode->Count - 1; else if (intKey == AFrom) { if (AIndex < pNode->Count - 1) { intNext = AIndex + 1; pNext = (pNode->Items[intNext].Key <= To) ? pNode : NULL; } } else if (AIndex == 0) pNext = NULL; else { intNext = AIndex--; pNext = (pNode->Items[intNext].Key <= To) ? pNode : NULL; } // 子结点 pNode = (TBTNode*)pNode->Item[AIndex].Link; } } // 返回结果 return boolRet ? pNode : NULL; } // 查找范围内的最后一项并返回序号(注: AFrom < ATo) TBTNode* FindLastItem(TBTNode* ARoot, long AFrom, long ATo, bool AIsInc, long& AIndex) { // 初始化 bool boolRet = false; TBTNode* pNode = ARoot; long intBegin, intEnd, intMid, intKey; // 循环查找层 while (pNode != NULL) { // 初始化(注: pNode->Count >= 1) intEnd = pNode->Count - 1; intBegin = 0; // 结点内二分查找 while (intBegin <= intEnd) { intMid = (intBegin + intEnd) >> 1; intKey = pNode->Items[intMid].Key; if (intKey < ATo) intBegin = intMid + 1; else { intEnd = intMid - 1; if (intKey == ATo) { intBegin = intMid; break; } } } // 判断是否为叶结点 AIndex = intBegin; if (pNode->IsLeaf) { if ((intKey == ATo) && AIsInc) boolRet = true; else if (AIndex > 0) { AIndex--; boolRet = (pNode->Items[AIndex].Key >= AFrom); } break; } else { // 校正索引 if ((intKey == ATo) && AIsInc) ; else if (AIndex > 0) AIndex--; else break; // 子结点 pNode = (TBTNode*)pNode->Item[AIndex].Link; } } // 返回结果 return boolRet ? pNode : NULL; }
