1. 跳表介绍
在之前关于数据结构的博客中介绍了两种基本数据结构：基于连续内存空间(线性表)的矢量和基于链接节点结构的链表。
[En]
Two basic data structures have been introduced in previous blogs on data structures: vectors based on continuous memory space (linear tables) and linked lists based on linked node structures.
有序的向量可以通过二分查找以logn对数复杂度完成随机查找，但由于插入/删除元素时可能导致内部数组内整体数据的平移复制，导致随机插入/删除的效率较低。而普通的一维链表结构虽然可以做到高效的插入/删除元素(只是关联的节点拓扑结构改变)，但是在随机查找时却效率较低，因为其只能从头/尾节点顺序的进行遍历才能找到对应节点。
计算机科学家发明了能够兼具向量与链表优点的平衡二叉搜索树(Balance Binary Search Tree BBST)，这其中红黑树是平均性能最高，也最复杂的一种BBST。
正是因为高性能的平衡二叉树过于复杂，使得计算机科学家另辟蹊径，发明了被称为 跳表(Skip List)的数据结构。跳表通过建立具有层次结构的索引节点，解决了普通链表无法进行二分查找的缺陷。跳表是基于链表的，因此其插入和删除效率和链表一样优秀；而由于索引节点的引入，也使得跳表可以以类似二分查找的形式进行特定元素的搜索，其查找性能也达到了O(logn)的对数复杂度，和有序向量以及平衡二叉树查询渐进时间复杂度一致。
总的来说，跳表是一个平均性能很优秀，结构相对简单的数据结构，在redis以及LevelDB、RocksDB等KV键值对数据库中被广泛使用。
2. 跳表工作原理
跳表查询
跳转表是具有多层索引节点的链表，最低层是链表，它保存所有原始数据节点。索引节点建立在最底层的链表节点上，索引节点的数量自下而上逐渐稀疏。
[En]
A jump table is a linked list with multi-tier index nodes, and the lowest level is a linked list, which holds all the original data nodes. The index node is built on the lowest linked list node, and the number of index nodes from bottom to top is gradually sparse.
在查询时，从最高层开始以 类似二分查找的方式 跳跃着的逐步向下层逼近查找最终的目标节点。