Idea
Idea
1. epoll中使用哈希表替换红黑树
对比来看，从时间来说
- 红黑树所有操作都是$O(log{n})$；哈希表是$O(1)$，但存在哈希碰撞问题，且扩容时需要复制全表，为$O(n)$。
从空间上看
红黑树是离散结构，不要求连续空间；哈希表是连续空间。
红黑树新增节点只需要分配节点内存；哈希表新增可能涉及扩容，扩容时需要占用更大空间。
树中元素有序，而哈系表元素无序。
为什么操作系统选用epoll而不是哈希表呢？
作为一个操作系统，需要做到尽量普适和稳定，对于哈希表扩容需要的双倍空间和$O(n)$的时间，是难以接受的。而epoll主要用于高并发场景，稳定性就更重要了，此外，占用双倍内存，对于一个数据量庞大的系统来说，双倍内存的花销也很大，利用率也不够高。
什么操作系统可能用到哈希表呢？
如果是哈希表作为存储结构的话，主要解决扩容的时间问题。由于是连续空间，空间问题似乎是不可避免的。
解决扩容的时间问题原理上是把扩容时间均摊。
后台线程扩容
当负载因子（load factor）达到一定阈值时，开启一个后台线程，首先开辟一块更大内存用于扩容，分配好后，操作如下。
- 查询时候就查询两个表，查到一个则返回。
- 插入时检查两个表是否都是没有，都没有则成功插入。
- 删除时需要尝试删除两个表的元素。
由于是后台线程，需要和用户线程做数据竞争，需要用到锁等同步机制。
不难发现，扩容的时间均摊出来了，但由于后台线程和用户线程竞争，锁占用花销很高。
渐进式哈希
顾名思义，将数据迁移分成多次迁移。不同与后台线程扩容，渐进式哈希不需要锁，扩容时间均摊到了用户的每次请求上。
渐进式 rehash 步骤如下：
- 给「哈希表 2」 分配空间；
- 在 rehash 进行期间，每次哈希表元素进行新增、删除、查找或者更新操作时，Redis 除了会执行对应的操作之外，还会顺序将「哈希表 1 」中索引位置上的所有 key-value 迁移到「哈希表 2」 上；
- 随着处理客户端发起的哈希表操作请求数量越多，最终在某个时间点会把「哈希表 1 」的所有 key-value 迁移到「哈希表 2」，从而完成 rehash 操作。
这样就巧妙地把一次性大量数据迁移工作的开销，分摊到了多次处理请求的过程中，避免了一次性 rehash 的耗时操作。
具体操作逻辑如下
- 查询时候就查询两个表，查到一个则返回。
- 插入时检查两个表是否都是没有，都没有则成功插入。
- 删除时需要尝试删除两个表的元素。
当负载因子超过阈值时，就开启rehash。
当然，如果一些数据迟迟不被用户请求，可能导致一直占用这部分空间无法释放。解决这一问题，可以在负载因子低到一定值的时候，可以让用户线程进行迁移或者请求后台线程迁移（当然需要做数据同步，比如加锁）。
那么什么情况可能用到哈希表呢？
解决了时间问题，如果能够接受内存的利用率低，数据无序的情况的话，就可以采用哈希表。总得来说，采用哈希表是一种激进的优化策略，只能适用极小部分场景。
2. MySQL中使用跳表替换B+树
由于MySQL是基于磁盘的，而磁盘的开销是主导的，所以重点落在减少磁盘IO上。
B+树的特性就是一个节点有多个子节点，叶子节点存储数据。
在Innodb中，一个节点就是一个页面，如果是叶子节点就存放数据，如果是非叶子节点就存放索引数据。
不难发现，B+树查找数据实际上就跟层高有关，有多少层，就需要经过多少个页面。
Innodb每次读取都是以页面为单位。读取时将页面加载到内存中进行操作，时机合适再写页面回磁盘。
我们以阶数M表示B+数一个节点最多有M个子节点。
假设M为5，我们发现，查找下一个页面时，都会找到5个子节点中的一个，进入这个子节点进行下一层的查找，即排除了这快数据里头的$\frac{4}{5}$，而和这5个子节点比较的过程是在内存进行的，开销远不及磁盘IO。这样，就实现了一次磁盘IO，排除了大部分数据的效果。如果是红黑树，是一次磁盘IO，仅仅排除$\frac{1}{2}$。
那跳表怎么做到一个页面，排除更大比例数据的效果呢？
答案是，修改层高函数，减小升层概率。
假如升层概率是$\frac{1}{2}$，则上一层的数据是下一层的一半，每次磁盘IO能够排除一半的数据。
假如升层概率是$\frac{1}{4}$，则上一层的数据是下一层的$\frac{1}{4}$，每次磁盘IO就能够排除$\frac{3}{4}$的数据。
假如升层概率是$\frac{1}{m}$，则上一层的数据是下一层的$\frac{1}{m}$，每次磁盘IO就能够排除$\frac{m-1}{m}$的数据。
不难发现，升层概率就类似于B+树的阶数。能够起到同样奇妙的效果。
除了减小升层概率之外，可以类比MySQL的页面那样，一个页面存放多条记录，记录由slot管理，页面内不同slot间使用二分查找加速。
此外，由于跳表本身结构简单，没有B+树复杂的旋转操作。
3. Redis为什么使用跳表而不使用B+树或红黑树呢?
redis支持多种数据结构，里面有个有序集合，也叫ZSET。内部实现就是跳表。那为什么要用跳表而不用B+树等结构呢?
Redis是基于内存的，无需考虑磁盘IO，所以层高就不再是劣势。同时，由于加层概率是1/4，所以判断一次可以排除1/4的数据，而B+树如果阶数大的话，一次能够排除的数据量少，效率就更低。
从内存占用上来比较，比平衡树更灵活一些。平衡树每个节点包含 2 个指针（分别指向左右子树），而跳表每个节点包含的指针数目平均为 1/(1-p)，具体取决于参数 p 的大小。如果像 Redis里的实现一样，取 p=1/4，那么平均每个节点包含 1.33 个指针，比平衡树更有优势。
并且前面也提到B+树是有一系列合并拆分操作的，换成红黑树或者其他AVL树的话也是各种旋转，目的也是为了保持树的平衡。
在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在跳表上进行范围查找就非常简单，只需要在找到小值之后，对第 1 层链表进行若干步的遍历就可以实现。
而跳表插入数据时，只需要随机一下，就知道自己要不要往上加索引，根本不用考虑前后结点的感受，也就少了旋转平衡的开销。
总结下来：
- 层高不再是劣势，查找比较次数更少。
- 内存占用更少
- 无需旋转平衡的开支。
- 范围查找操作更简单。
- 编码实现、调试简单。
所以选择的是跳表。