面试真题

结论：跳表是基于有序链表加多层索引实现二分查找的数据结构；相比红黑树，跳表区间查询更高效、实现简单、并发控制更容易。原理：底层是有序单向链表，每层以概率p（如0.25）向上建索引，平均查找O(log n)；红黑树是平衡二叉搜索树，查找也是O(log n)。不使用红黑树的原因：1.跳表区间遍历只需遍历底层链表，红黑树需中序遍历较复杂；2.跳表插入删除只需修改相邻节点指针，红黑树需旋转调色；3.并发下跳表可无锁（如RocksDB用原子操作），红黑树旋转难无锁。