B 树搜索算法
在索引搜索算法中，无论是升序还是降序排列，我们都是基于键的权值而非直接使用键值来进行操作的。关于搜索的具体操作和规则，这里有一些需要说明的地方。为了更好地帮助您理解键搜索是如何生成结果集的，我们可以看一个简单的例子：假设有一个包含整数字段的键，其数据集为[1,2,2,3,4,4,5]。
接下来的表格展示了在执行搜索操作之后，各个键值及其对应的权重情况。
| 键值 | 权重 |
|---|---|
| 1 | 0 |
| 2 | 1 |
| 2 | 1 |
| 3 | 2 |
| 4 | 3 |
| 4 | 3 |
| 5 | 4 |
现在考虑一个稍微复杂一点的例子，其中键表示为包含两个字段的结构：一个整数和一个字符串。比较函数像上面的示例那样比较整数，并将字符缓冲区作为 ASCII 字符进行比较。假设数据集如下：
[ (1,"ZZZ"), (1,"BBB"), (2,"AAA"), (2,"AAA"), (2,"BBB"), (3,"XXX") ]得出的密钥权重表为：
| 键值 | 权重 |
|---|---|
| 1, “BBB” | 0 |
| 1, “ZZZ” | 1 |
| 2, “AAA” | 2 |
| 2, “AAA” | 2 |
| 2, “BBB” | 3 |
| 3, “XXX” | 4 |
如果索引是反向顺序（声明为“降序”），则权重表将如下所示：
| 键值 | 权重 |
|---|---|
| 5 | 0 |
| 4 | 1 |
| 4 | 1 |
| 3 | 2 |
| 2 | 3 |
| 2 | 3 |
| 1 | 4 |
| 键值 | 权重 |
|---|---|
| 3, “XXX” | 0 |
| 2, “BBB” | 1 |
| 2, “AAA” | 2 |
| 2, “AAA” | 2 |
| 1, “ZZZ” | 3 |
| 1, “BBB” | 4 |
在B-Tree索引中，我们有五种带有内部操作码的搜索操作：MCO_LT、MCO_LE、MCO_EQ、MCO_GE和MCO_GT。当您执行搜索操作时，可以选择其中一个操作代码，结果将通过游标返回，并定位到索引中的适当元素。
为了便于理解，我们将“指定键值的权重”简写为WSKV，将“光标的当前元素”简写为CCE。下表展示了这些概念如何通过SmartEDB运行时相互关联：
| 查询操作 | 查询条件 | 规则描述 |
|---|---|---|
| MCO_LT | 小于（<） | 将CCE指向权值为WSKV-1 |
| MCO_LE | 小于或等于（<=） | 将CCE指向权值等于WSKV的键的最后一个（最右边）出现，或者（如果没有找到）指向权值为WSKV-1的第一个键 |
| MCO_EQ | equal(==) | 将CCE指向权重等于WSKV |
| MCO_GE | 大于或等于（>=） | 将CCE指向权值等于WSKV的键中第一个（最左边）出现的键，或者（如果没有找到）指向权值为WSKV+1的第一个键 |
| MCO_GT | 大于（>） | 将CCE指向权重为WSKV+1的第一个键 |
为了说明这些规则，考虑上面的第一个示例数据集以及搜索值 2。下表展示了游标的位置以及 prev（前一个）和 next（后一个）游标导航操作的结果：
| 查询操作 | 查询条件 | 规则描述 |
|---|---|---|
| MCO_LT | 1 = CCE 2 2 3 4 4 5 | CCE指向键值1；prev将返回‘ MCO_S_CURSOR_END ’；next将返回‘ MCO_S_OK ’并将CCE移动到键值2 |
| MCO_LE | 1 2 2 = CCE 3 4 4 5 | CCE指向最右边的键值2；prev将返回‘ MCO_S_OK ’并将CCE移动到键值2（最左边）next将返回‘ MCO_S_OK ’并将CCE移动到键值3 |
| MCO_EQ | 1 2 = CCE 2 3 4 4 5 | CCE指向最左边的键值2；prev将返回‘ MCO_S_OK ’并将CCE移动到键值1next将返回‘ MCO_S_OK ’并将CCE移动到键值2（最右边） |
| MCO_GE | 1 2 = CCE 2 3 4 4 5 | CCE指向最左边的键值2；prev将返回‘ MCO_S_OK ’并将CCE移动到键值1next将返回‘ MCO_S_OK ’并将CCE移动到键值2（最右边） |
| MCO_GT | 1 2 2 3 = CCE 4 4 5 | CCE指向键值3；prev将返回‘ MCO_S_OK ’并将CCE移动到键值2（最右边）next将返回‘ MCO_S_OK ’并将CCE移动到键值4（最左边） |
在反向索引的情况下，同样以搜索值 2 为例：
| 查询操作 | 查询结果 | 结果描述 |
|---|---|---|
| MCO_LT | 5 4 4 3 = CCE 2 2 1 | CCE指向键值3；prev将返回‘ MCO_S_OK ’并将CCE移动到键值4（最右边）next将返回‘ MCO_S_OK ’并将CCE移动到键值2（最左边） |
| MCO_LE | 5 4 4 3 2 2= CCE 1 | CCE指向键值2；prev将返回‘ MCO_S_OK ’并将CCE移动到键值2（最左边）next将返回‘ MCO_S_OK ’并将CCE移动到键值1 |
| MCO_EQ | 5 4 4 3 2 = CCE 2 1 | CCE指向键值2；prev将返回‘ MCO_S_OK ’并将CCE移动到键值3next将返回‘ MCO_S_OK ’并将CCE移动到键值2（最右边） |
| MCO_GE | 5 4 4 3 2 = CCE 2 1 | CCE指向键值2；prev将返回‘ MCO_S_OK ’并将CCE移动到键值3next将返回‘ MCO_S_OK ’并将CCE移动到键值2（最右边） |
| MCO_GT | 5 4 4 3 2 2 1 = CCE | CCE指向键值1；prev将返回‘ MCO_S_OK ’并将CCE移动到键值2（最右边）next将返回‘ MCO_S_CURSOR_END ’ |
优化树索引
通常，B 树实现不会在索引中存储键值。然而，对于内存数据库，有时将键值保留在索引页中是有益的。请参阅本文档中的“包含键值和覆盖索引”部分。