面试真题

结论：跳表（Skip List）是一种支持有序元素快速查找的随机化数据结构，可视为加了多层索引的链表。原理：底层为有序单向链表；每个节点以概率p（常用0.25或0.5）晋升到上一层，形成稀疏索引；查找时从最高层向右，遇较大值下降，直至底层，平均复杂度O(log n)。插入删除先查再改指针，无需旋转。常用于Redis有序集合、RocksDB MemTable。优点：实现简单、区间查询友好、易并发。