月度归档:2015年11月

LevelDB阅读笔记 之 SkipList

在leveldb中,插入与查找操作是高频操作、无删除操作。因此使用物理上线性的有序结构是不现实的,那么就是经典的二叉有序树及其变种,如AVL、红黑树甚至B\B+树,但这类数据结构都会牵扯到一个问题:随着节点的插入,需要频繁地进行平衡调节。而且为了保证线程安全,在平衡调节时需要锁住大面积地子树。而有一种以随机概率思想实现的类似平衡树的线性表结构:跳表,具体见论文继续阅读