最近学习系统设计，这个名词多次出现，于是乎研究了一下。 还挺有意思。

这是一种较新的数据结构，1989年William Pugh首次提出，主要用于Redis的内部结构

为了实现有序数据的快速查找和修改。

一般来说，首先会想到红黑树，在保证数据有序的情况同时，能够实现O(logn)的查询和修改。

基本思路

• 有序数组利用二分法可以在O(logn)完成查找，但是增删数据将要导致整个数组移动
• 链表可以完成O(1)的时间进行增删，但如果想要查找就需要遍历整个列表O(n)
• 如何利用链表的特点同时实现快速查找

原理很简单，在有序链表的基础上，依次建立更高一层的数据量减半的链表，这样的话就保证查找元素只需要O(logn)时间既可。 如下，在更新的时候同时要做多处的修改。

1         ->        5         ->       9

|		            |                  |

1    ->   3     ->  5    ->   7   ->   9

|		  |         |         |        |

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9