3、skip-list跳表

一、定义

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

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

二、跳表的实现

image-20230422100426672

三、复杂度

• 时间负载度 Olog(N)

• 空间复杂度O(N)

四、优缺点

优点

跳表是一个最典型的空间换时间解决方案，而且只有在数据量较大的情况下才能体现出来优势。而且应该是读多写少的情况下才能使用，所以它的适用范围应该还是比较有限的

缺点

维护成本相对要高 - 新增或者删除时需要把所有索引都更新一遍；
最后在新增和删除的过程中的更新，时间复杂度也是O(log n)