内存数据库

• 图a中，所有元素按序排列，被存储在一个链表中，则一次查询之多需要比较N个链表节点；
• 图b中，每隔2个链表节点，新增一个额外的指针，该指针指向间距为2的下一个节点，如此以来，借助这些额外的指针，一次查询至多只需要⌈n/2⌉+ 1次比较；
• 图c中，在图b的基础上，每隔4个链表节点，新增一个额外的指针，指向间距为4的下一个节点，一次查询至多需要⌈n/4⌉+ 2次比较；

• 首先根据跳表的高度选取最高层的头节点；
• 若跳表中的节点内容小于查找节点的内容，则取该层的下一个节点继续比较；
• 若跳表中的节点内容等于查找节点的内容，则直接返回；
• 若跳表中的节点内容大于查找节点的内容，且层高不为0，则降低层高，且从前一个节点开始，重新查找低一层中的节点信息；若层高为0，则返回当前节点，该节点的key大于所查找节点的key。

• 在查找的过程中，不断记录每一层 的前任节点 ，如图中红色圆圈所表示的；
• 为新插入的节点随机产生层高（随机产生层高的算法较为简单，依赖最高层数和概率值p，可见下文中的代码实现）；
• 在合适的位置插入新节点（例如图中节点12与节点19之间），并依据查找时记录的前任节点信息，在每一层中，以链表插入 的方式，将该节点插入到每一层的链接中。

func (p *DB) randHeight() (h int) {
    const branching = 4
    h = 1
    for h < tMaxHeight && p.rnd.Int()%branching == 0 {
        h++
    }
    return
}

• 若迭代器刚被创建，则根据用户指定的查找范围[Start,Limit)找到一个符合条件的跳表节点；
• 若迭代器处于中部，则取出上一次访问的跳表节点的后继节点，作为本次访问的跳表节点（后继节点为最底层的后继节点）；
• 利用跳表节点信息（keyvalue数据偏移量，key，value值长度等），获取keyvalue数据；

• 若迭代器刚被创建，则根据用户指定的查找范围[Start,Limit）在跳表中找到最后一个符合条件的跳表节点；
• 若迭代器处于中部，则利用上一次访问的节点的key值，查找比该key值更小的跳表节点；
• 利用跳表节点信息（keyvalue数据偏移量，key，value值长度等），获取keyvalue数据；

• 用户定义的key：这个key值也就是原生的key值；
• 序列号：leveldb中，每一次写操作都有一个sequencenumber，标志着写入操作的先后顺序。由于在leveldb中，可能会有多条相同key的数据项同时存储在数据库中，因此需要有一个序列号来标识这些数据项的新旧情况。序列号最大的数据项为最新值；
• 类型：标志本条数据项的类型，为更新还是删除；

• 首先按照字典序比较用户定义的key（ukey），若用户定义key值大，整个internalKey就大；
• 若用户定义的key相同，则序列号大的internalKey值就小；

type DB struct {
    cmp comparer.BasicComparer
    rnd *rand.Rand
 
    mu     sync.RWMutex
    kvData []byte
    // Node data:
    // [0]         : KV offset
    // [1]         : Key length
    // [2]         : Value length
    // [3]         : Height
    // [3..height] : Next nodes
    nodeData  []int
    prevNode  [tMaxHeight]int
    maxHeight int
    n         int
    kvSize    int
}

• 第一个字节用来存储本节点key-value数据在kvData中对应的偏移量；
• 第二个字节用来存储本节点key值长度；
• 第三个字节用来存储本节点value值长度；
• 第四个字节用来存储本节点的层高；
• 第五个字节开始，用来存储每一层对应的下一个节点的索引值；