3、skip-list跳表

一、定义

跳表是可以实现二分查找的有序链表，跳表=链表+多级索引

skiplist是一种以空间换取时间的结构。由于链表，无法进行二分查找，因此借鉴数据库索引的思想，提取出链表中关键节点（索引），先在关键节点上查找，再进入下层链表查找。提取多层关键节点，就形成了跳跃表

二、跳表的实现