LevelDB源码解析(2) SkipList(跳跃表)
背景 SkipList是LevelDB的MemTable使用的底层存储结构，LevelDB实现了一个支持泛型的跳跃表。本文不会具体介绍跳跃表的数据结构，如果读者不了解跳跃表的原理、实现，可以先看一下跳跃表（Skiplist）从原理到实现 SkipList的对外……
包含标签 跳跃表 的文章
跳跃表（SkipList）从原理到实现
数组与链表 数组和链表是非常基础的两种数据结构，链表每次查找都需要从头结点开始线性遍历，时间复杂度是O(n)。而数组通过维护元素顺序可以使用二分查找，查找的时间复杂度是O(lg(n))。查找效率方面数组完胜链表。 但是由于数组插入或删除元素时必须要移动所有受影……