范围查询
B+树迭代器
迭代器接口
B+树的基本操作包括用于范围查询的查找和迭代。B+树的位置由状态化的迭代器 BIter 表示。
// 查找小于或等于输入键的最近位置
func (tree *BTree) SeekLE(key []byte) *BIter
// 获取当前键值对
func (iter *BIter) Deref() ([]byte, []byte)
// Deref() 的前置条件检查
func (iter *BIter) Valid() bool
// 向前或向后移动
func (iter *BIter) Prev()
func (iter *BIter) Next()
例如，对于查询 a <= key 的操作可以这样实现：
for iter := tree.SeekLE(key); iter.Valid(); iter.Prev() {
k, v := iter.Deref()
// ...
}
导航树结构
为了在节点内找到当前键的兄弟键，需要知道当前键的位置。如果兄弟键位于兄弟节点中，则需要回溯到父节点。由于不使用父指针，因此需要从根到叶的完整路径。
type BIter struct {
tree *BTree
path []BNode // 根到叶的路径
pos []uint16 // 节点中的索引
}
移动迭代器类似于逐位递增数字时的进位操作。
func (iter *BIter) Next() {
iterNext(iter, len(iter.path)-1)
}
func iterNext(iter *BIter, level int) {
if iter.pos[level]+1 < iter.path[level].nkeys() {
iter.pos[level]++ // 在当前节点内移动
} else if level > 0 {
iterNext(iter, level-1) // 移动到兄弟节点
} else {
iter.pos[len(iter.pos)-1]++ // 超出最后一个键
return
}
if level+1 < len(iter.pos) { // 更新子节点
node := iter.path[level]
kid := BNode(iter.tree.get(node.getPtr(iter.pos[level])))
iter.path[level+1] = kid
iter.pos[level+1] = 0
}
}
查找键
查找键类似于点查询，但会记录路径。
func (tree *BTree) SeekLE(key []byte) *BIter {
iter := &BIter{tree: tree}
for ptr := tree.root; ptr != 0; {
node := tree.get(ptr)
idx := nodeLookupLE(node, key)
iter.path = append(iter.path, node)
iter.pos = append(iter.pos, idx)
ptr = node.getPtr(idx)
}
return iter
}
nodeLookupLE 是用于小于等于比较的函数，你还需要其他比较操作符。
const (
CMP_GE = +3 // >=
CMP_GT = +2 // >
CMP_LT = -2 // <
CMP_LE = -3 // <=
)
func (tree *BTree) Seek(key []byte, cmp int) *BIter
9.2 保持顺序的编码
对任意数据进行字节字符串排序
我们的B+树处理的是任意字节的字符串键，但列可以是其他类型的数据，如数字，而且键可以是多个列。为了支持范围查询，序列化后的键必须根据其数据类型进行比较。
一种明显的方法是用一个回调函数替换 bytes.Compare，该回调函数根据表模式解码并比较键。另一种方法是选择一个特殊的序列化格式，使得生成的字节能够反映排序顺序。这是我们将采用的快捷方式。
数字
首先解决一个简单的问题：如何编码无符号整数，以便可以通过 bytes.Compare 比较它们？bytes.Compare 逐字节工作直到遇到差异。因此，在比较中第一个字节是最显著的。如果我们首先放置整数的最高有效（高位）位，那么它们就可以逐字节比较了。这正是大端整数。
接下来考虑有符号整数，它通过补码表示。在补码表示中，无符号值的上半部分只是偏移到负值。为了确保正确的顺序，正半部分与负半部分交换，这仅仅是翻转最高有效位。
var buf [8]byte
u := uint64(v.I64) + (1 << 63)
// 翻转符号位
binary.BigEndian.PutUint64(buf[:], u) // 大端
一些例子：
int64 | Encoded bytes
--------|-----------------
MinInt64| 00 00 00 00 00 00 00 00
-2 | 7f ff ff ff ff ff ff fe
-1 | 7f ff ff ff ff ff ff ff
0 | 80 00 00 00 00 00 00 00
1 | 80 00 00 00 00 00 00 01
MaxInt64| ff ff ff ff ff ff ff ff
一般思路：
- 排列比特，使更高有效位先出现（大端）。
- 将比特重新映射为按正确顺序排列的无符号整数。
练习：将此应用于浮点数（符号+量级+指数）。
字符串
键可以是多列，但是 bytes.Compare 只适用于单个字符串列，因为它需要长度。我们不能简单地连接字符串列，因为这会造成歧义。例如，(“a”, “bc”) vs (“ab”, “c”)。
有两种编码带有长度的字符串的方式，一种是在前面添加长度，这需要解码；另一种是在末尾放一个分隔符，比如空字节。前面的例子编码为 "a\x00bc\x00" 和 "ab\x00c\x00"。
分隔符的问题在于输入中不能包含分隔符，这通过转义分隔符来解决。我们将使用字节 0x01 作为转义字节，并且转义字节本身也必须被转义。所以我们需要两种转换：
00 -> 01 01
01 -> 01 02
注意，转义序列仍然保留排序顺序。
元组
多列比较（元组）是逐列进行的，直到遇到差异为止。这就像字符串比较一样，除了每个项是一个类型值而不是字节。只要没有歧义，我们可以简单地串联每个列的编码字节。
9.3 范围查询
扫描器（Scanner）
扫描器是B+树迭代器的一个封装，它将键值对解码为行数据。
Valid()：判断当前是否在范围内。Next()：移动底层的B树迭代器。Deref(rec *Record)：获取当前行。db.Scan(table string, req *Scanner) error：执行范围查询并返回结果。
// 是否在范围内？
func (sc *Scanner) Valid() bool
// 移动底层的B树迭代器
func (sc *Scanner) Next()
// 获取当前行
func (sc *Scanner) Deref(rec *Record)
func (db *DB) Scan(table string, req *Scanner) error
输入是一个主键的区间。Scanner 结构体定义如下：
type Scanner struct {
// 范围，从Key1到Key2
Cmp1 int // CMP_?? 比较操作符
Cmp2 int
Key1 Record // 起始键
Key2 Record // 结束键
// ...
}
对于开区间的情况，只需将 Key2 设置为最大或最小值即可。
9.4 我们学到了什么
- B+树迭代器：我们了解了如何使用状态化的迭代器遍历B+树，包括查找特定键、向前向后移动等操作。
- 保持顺序的编码：学习了如何对不同类型的数据进行编码，以确保它们在字节级别上保持正确的顺序。这对于支持范围查询至关重要。
下一步将是添加二级索引，这实际上就是额外的表结构，用于加速某些类型的查询。例如，一个二级索引可以用来快速查找符合特定条件的所有记录，而不需要遍历整个主表。这涉及到创建新的表来存储索引信息，并实现相应的查询逻辑以便于利用这些索引来提高查询效率。
代码仓库地址：database-go