◄ 上一步目录下一步 ►

0405: 范围查询

KV 范围查询

上一步的 Seek() 函数只能做开放区间的的查询（key >= 123）：

func (kv *KV) Seek(key []byte) (*KVIterator, error)

现在增加一个闭合区间的查询接口：

func (kv *KV) Range(start, stop []byte, desc bool) (*RangedKVIter, error)

desc 参数控制遍历顺序，可以用来实现 ORDER BY：

desc == false，查询 start <= key && key <= stop。
desc == true，查询 start >= key && key >= stop。

新增的 RangedKVIter 只是把原来的 KVIterator 包装一下：

type RangedKVIter struct {
    iter KVIterator
    stop []byte
    desc bool
}
func (iter *RangedKVIter) Key() []byte { return iter.iter.Key() }
func (iter *RangedKVIter) Val() []byte { return iter.iter.Val() }

遍历时增加了一个终止条件：

func (iter *RangedKVIter) Valid() bool {
    if !iter.iter.Valid() {
        return false
    }
    r := bytes.Compare(iter.iter.Key(), iter.stop)
    if iter.desc && r < 0 {
        return false
    } else if !iter.desc && r > 0 {
        return false
    }
    return true
}

Next() 函数要判断遍历顺序：

func (iter *RangedKVIter) Next() error {
    if !iter.Valid() {
        return nil
    }
    if iter.desc {
        return iter.iter.Prev()
    } else {
        return iter.iter.Next()
    }
}

Range() 的实现也是包装原来的 Seek()，读者自己实现。注意可能要调整迭代器的初始位置，因为 Seek() 是 ≥，而 Range() 可以是 ≥ 或 ≤。

func (kv *KV) Range(start, stop []byte, desc bool) (*RangedKVIter, error) {
    iter, err := kv.Seek(start)
    if err != nil {
        return nil, err
    }
    // TODO
}

前缀比较

现在给 DB 也加上类似的 Range() 接口。有个新问题：数据库的主键或索引，是可以由多个列组成的，查询时可以只用到一部分前缀。比如主键是 (a, b, c)，可以做这些查询：

(a, b, c) ≤ (123, 4, 5)，使用完整 key 的查询。参见 0403 步的 tuple 比较。
(a, b) ≤ (123, 4)，使用 (a, b, c) 的前缀 (a, b)，相当于 (a, b, c) ≤ (123, 4, +∞)。
a ≤ 123，使用 (a, b, c) 的前缀 (a, )，相当于 (a, b, c) ≤ (123, +∞)。

将前缀 (123, 4) 编码后在 KV 里做 K ≤ (123, 4) 的查询，实际得到 (a, b, c) < (123, 4)。所以我们引入了无穷的概念，将前缀补齐成完整的 key。可以将4种前缀比较操作都转换成完整的 key 比较：

前缀	完整
(a, b) < (1, 2)	(a, b, c) ≤ (1, 2, −∞)
(a, b) ≤ (1, 2)	(a, b, c) ≤ (1, 2, +∞)
(a, b) > (1, 2)	(a, b, c) ≥ (1, 2, +∞)
(a, b) ≥ (1, 2)	(a, b, c) ≥ (1, 2, −∞)

如果我们修改 KV 里 K 的编码，将无穷包含进去，就能实现前缀比较了。新增一个用来编码 key 前缀的函数：

func EncodeKeyPrefix(schema *Schema, prefix []Cell, positive bool) []byte

positive 参数决定编码是以 +∞ 还是 −∞ 结尾。用以下方式编码无穷：

空字符串表示 −∞，也就是比较顺序最小的字符串。这要求数据序列化后不能是""。
"\xff" 表示 +∞，也就是一个字节的最大值。这要求数据序列化后不能以 "\xff" 开头。

第一个要求已经满足。而第二个要求，可以在每列前面增加一个字节，避开 0xff：

func (row Row) EncodeKey(schema *Schema) []byte {
    key := append([]byte(schema.Table), 0x00)
    for _, idx := range schema.PKey {
        cell := row[idx]
        key = append(key, byte(cell.Type))  // 避开 0xff
        key = cell.EncodeKey(key)
    }
    return append(key, 0x00)                // > -∞
}

由于 −∞ 的编码是空字符串，要避免 (a, b) 和 (a, b, −∞) 编码冲突，在末尾增加一个 0x00 字节，正好大于 −∞。

func EncodeKeyPrefix(schema *Schema, prefix []Cell, positive bool) []byte {
    key := append([]byte(schema.Table), 0x00)
    for i, cell := range prefix {
        key = append(key, byte(cell.Type))  // 避开 0xff
        key = cell.EncodeKey(key)
    }
    if positive {
        key = append(key, 0xff)             // +∞
    }                                       // -∞
    return key
}

DB 范围查询

增加查询闭合的区间的接口（支持4种比较操作）：

type ExprOp uint8

const (
    OP_LE ExprOp = 12 // <=
    OP_GE ExprOp = 13 // >=
    OP_LT ExprOp = 14 // <
    OP_GT ExprOp = 15 // >
)

type RangeReq struct {
    StartCmp ExprOp // <= >= < >
    StopCmp  ExprOp
    Start    []Cell
    Stop     []Cell
}

func (db *DB) Range(schema *Schema, req *RangeReq) (*RowIterator, error)

遍历的方向由 StartCmp 决定，>= 和 > 升序，否则降序。 Start 和 Stop 可以是完整的主键，也可以是前缀，长度不需要一样。

RowIterator 里的 KVIterator 替换成这次新增的 RangedKVIter：

type RowIterator struct {
    schema *Schema
    iter   *RangedKVIter // 替换
    valid  bool
    row    Row
}

剩下的读者可以自己实现：

func (db *DB) Range(schema *Schema, req *RangeReq) (*RowIterator, error) {
    start := EncodeKeyPrefix(schema, req.Start, suffixPositive(req.StartCmp))
    stop := EncodeKeyPrefix(schema, req.Stop, suffixPositive(req.StopCmp))
    desc := isDescending(req.StartCmp)
    iter, err := db.KV.Range(start, stop, desc)
    if err != nil {
        return nil, err
    }
    // TODO
}

您正在阅读免费版教程，从第4章起只有简单的指引，适合爱好挑战和自学的读者。
可以购买有详细指导+背景知识的完整版。

◄ 上一步目录下一步 ►