Interpretation of leveldb source code skiplist

LevelDB Medium jump table

Basic overview

levelDB The data stored in memory is stored in Memtable Medium , among Memtable The underlying data structure is based on Jump watch To achieve .

among Memtable There will be frequent insert and query operations , The delete operation is simulated as inserting a with （ Delete ） Label data , You need to support traversal

Multithreading support

When multithreading operations, we need to ensure some ：

Writes require external synchronization, most likely a mutex.

Reads require a guarantee that the SkipList will not be destroyed

• Write: Lock the user when modifying the skip table
• Read： When accessing the jump table, ensure that the jump table will not be destroyed

Through atomic operation , Make it possible to Read concurrent , Read write concurrent thread safety , however Write concurrent Users are required to maintain

leveldb Appointment

• node It will not be deleted unless the entire jump table structure is destroyed
• node Nodes except next Everything outside the pointer is unchanged

The implementation of skip table

Reference code