0401: Sorting and Search

Sorting and Range Queries

The current SQL can only operate on a single row by primary key. This is limited by the KV interfaces with only get, set, del operations. Now add features:

• Scan a table.
• Query a primary key range, like a > 123 or 123 < a AND a < 456.
• Sort results (ORDER BY).

These are the same idea: iterate in sorted order.

• Table scan: same as range -∞ < a AND a < +∞.
• Range query: find bounds, then iterate in order.
• Sorting: ORDER BY just controls direction.

Now replace the KV map with a simple array, which will involve into an LSM-Tree later.

type KV struct {
    log  Log
    keys [][]byte
    vals [][]byte
}

Binary Search

The standard library has binary search, but you should implement it yourself at least once. It looks simple, but many people struggle to code it.

func BinarySearchFunc(x S, target T, cmp func(E, T) int) (pos int, ok bool)

If the key is found, return ok=true.

func (kv *KV) Get(key []byte) (val []byte, ok bool, err error) {
    if idx, ok := slices.BinarySearchFunc(kv.keys, key, bytes.Compare); ok {
        return kv.vals[idx], true, nil
    }
    return nil, false, nil
}

If ok=false, the returned position is where the key should be inserted, which can be used in SetEx().

func (kv *KV) SetEx(key []byte, val []byte, mode UpdateMode) (bool, error) {
    idx, exist := slices.BinarySearchFunc(kv.keys, key, bytes.Compare)
    // TODO
}

The standard library also provides slices.Insert() and slices.Delete().

Database Initialization

Update KV.Open() to read the log into arrays:

func (kv *KV) Open() error

Until LSM-Tree is implemented, all data has to be loaded into memory.