level 4 50
level 3 10 50 70 100
level 2 1 10 30 50 70 100
level 1 1 3 10 30 50 70 100
level 0 1 3 5 10 30 40 50 60 70 100
墨尔本大学计算机本科实验作业，使用C语言实现一个简单的SkipList结构。受此启发，本项目在此之上实现一个强化版本的SkipList。
SkipList作为B+Tree的一种替代品具有很多的应用场景，著名的Google/leveldb中的内存表就是使用SkipList作为存储结构，其性能可以与B+Tree相媲美。
更多有关SkipList的算法设计和理论分析参考skiplist1990.pdf论文
项目构建按照标准的C++项目格式，包含完整的代码测试。
.
├── build //项目构建文件夹
├── build_support // 构建项目支持文件夹
├── CMakeLists.txt
├── notes // 笔记
├── readme.md
├── resources // 项目资源
├── src // 项目源码
├── test // 测试文件
└── third_party // 第三方库支持
项目预留了增删查改基本的操作，以及文件插入和输出SkipList。
- Insert(key, value)
- Remove(key)
- Lookup(key, result)
- InsertFromFile(filename)
- Print()
SkipList中需要控制的超参数主要有：
- 高度(max_height)。SkipList的高度需要控制，一般来讲高度设置在12左右差不多可以满足需求
- 概率(branching)。每个元素以多大的概率(1/branching)增加高度，一般设置branching为2，即概率为1/2
- 比较器(comparator)。由于需要按照key进行排序，所以需要自定义key的大小比较函数（仿生函数）
mkdir build && cd build
cmake ..
make skiplist_sequential_test
./test/skiplist_sequential_test
make skiplist_concurrent_test
./test/skiplist_concurrent_test
make skiplist_performance_test
./test/skiplist_performance_test
将./src目录下的头文件和源文件放入项目编译即可。
如果需要自定义Key, Value类型，只需做如下两个步骤即可。
- 在
generic_key.h中添加Key Value类型 - 在
skiplist.cpp文件中最后一行加入template class SkipList<GenericKey<8>, GenericValue<8>, GenericComparator<8>>;来预定义。
TODO
- 编码格式。遵循Google C++ Style编写
- 代码抽象。将Key, Value抽象出来, 支持多种类型
- 并发模块。Reader Writer Latch, 支持并发读。
- 测试模块。使用GTest对源码测试，包括正确, 并发, 性能
- 迭代器。 能够使用迭代器访问SkipList,
for (auto iter : skiplist) - 内存管理。涉及到内存的分配，C++最头疼的是需要程序员自行管理内存。