LevelDB源码解读-SkipList

LevelDB中跳表

基本概述

levelDB中存储在内存中的数据就是存储在Memtable中的, 其中Memtable底层的数据结构就是基于 跳表来实现的。

其中Memtable会有很频繁的插入和查询的操作，删除操作被模拟为是插入一个带有（删除）标签的数据，需要支持遍历操作

多线程的支持

多线程进行操作的时候我们需要保证的一些：

Writes require external synchronization, most likely a mutex.

Reads require a guarantee that the SkipList will not be destroyed

• Write:修改跳表的时候对用户进行加锁
• Read：访问跳表的时候保证跳表不会被销毁掉

通过原子性的操作，使得能够实现 读读并发，读写并发线程安全， 但是 写写并发需要使用者自行维护

leveldb约定

• node不会被删除除非整个跳表结构都被销毁掉
• node节点除了next指针之外都是不变的

跳表的实现

参考代码