0604: 合并数据结构

合并 KV

要将 SSTable 加入到项目中，加上 MemTable（对应 log），就会有2个数据结构。更新时，key 先进入到 MemTable，最终被合并进 SSTable，所以查询时可能要查询2个数据结构。

后面要实现的 LSM-Tree，可以有多层 SSTable，下层的 SSTable 是从上层合并而来。查询单个 key 时从上到下，逐层查询。

如果是范围查询，就要用到排序算法里最简单的 merge sort。

Merge sort

我们实现k个范围的合并，可以沿用到后面的 LSM-Tree，这并不比合并2个范围复杂。

type MergedSortedKV []SortedKV

func (m MergedSortedKV) Iter() (iter SortedKVIter, err error) {
    levels := make([]SortedKVIter, len(m))
    for i, sub := range m {
        if levels[i], err = sub.Iter(); err != nil {
            return nil, err
        }
    }
    return &MergedSortedKVIter{levels, levelsLowest(levels)}, nil
}

type MergedSortedKVIter struct {
    levels []SortedKVIter
    which  int
}
func (iter *MergedSortedKVIter) Valid() bool {
    return iter.which >= 0
}
func (iter *MergedSortedKVIter) Key() []byte {
    return iter.levels[iter.which].Key()
}
func (iter *MergedSortedKVIter) Val() []byte {
    return iter.levels[iter.which].Val()
}
func (iter *MergedSortedKVIter) Next() error
func (iter *MergedSortedKVIter) Prev() error

which 记录了当前最小/最大的那个 iterator。读者自己实现。要求：

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