上海网站策划,网站建设中啥意思,做彩票网站多少钱,深圳实惠的专业建站公司class SkipList
class SkipList 是Level DB中的重要数据结构#xff0c;存储在memtable中的数据通过SkipList来存储和检索数据#xff0c;它有优秀的读写性能#xff0c;且和红黑树相比#xff0c;更适合多线程的操作。
SkipList
SkipList还是一个比较简单的数据结构存储在memtable中的数据通过SkipList来存储和检索数据它有优秀的读写性能且和红黑树相比更适合多线程的操作。
SkipList
SkipList还是一个比较简单的数据结构它首先是一个List链表读写操作也和List相差不大。SkipList的复杂之处是每一个Node有一个高度的信息带有这个高度信息的Node可以看成一个Node Array [Height]其中的Height小于或等于SkipList 的 Max Height如图1所示。 图1. Max Height 4 s SkipList
当我们需要往这个SkipList里面添加一个Node的时候这个新的Node他有不同的概率得到Height如图2所示key 7 的 node它有probability概率 p height 1有probability概率 (1 - p) * p height 2有probability概率 (1 - p)* (1 - p) * p height 3最后它有probability概率 1 - other probabilityheight 4。 图2. Max Height 4 s SkipList insert key 7
Level DB 中的实现
Level DB中实现了class SkipList下面来梳理总结一下这个SkipList的一些特点。
原子操作
在操作上Level DB中的SkipList的数据都采用了原子操作且仅支持find 和 insert 不支持delete例如std::atomicNode* next_std::atomicint max_height_ 由于这些原子操作所以在多线程的情况下不再需要额外的mutex操作。
memory order
对于原子操作memory order 是在多核处理器上每一个CPU看到的不同的上下文的表征。在SkipList里面对于单纯的原子互斥操作使用了std::memory_order_relaxed。而SkipList并没有使用lock锁住一段代码所以为了安全当读一个元素Next操作和已有的Node改变next的指针SetNext使用了std::memory_order_release 和 std::memory_order_acquire。也就是在读的时候要考虑到写的前序上下文都已经完成。
