这两天有小伙伴问我一个问题，为什么redis的zset用跳跃表，不用b+ tree？
我先不说结论，我先说下 跳跃表 和B+tree 。
跳跃表在之前的 《redis源码阅读-zset》 中，已经详解了zset的使用跳跃表的源码，今天借用下之前的图片。
zset在演化为跳跃表以后，主要有两块
一块以*dict 存储的 元素与分值的hash映射一块以*zsl 存储的跳跃表的信息 关键是*header的一个64级的数组（可以理解为hashmap的桶结构）第0层是所有数据的以score排序的双向链表第1~63层是是构建出来的跳跃表，也是双向链表在插入数据的时候会随机生成 层级（每一个元素都有可能是0~63级），从上到下查找并插入在查找数据的时候，有分值直接查，没分值先从*dict获取对应元素的分值在这里我们一定要注意几个点，
元素的层级结构双向链表举个例子，见下图
插入：
假如有socre=30、25、45 这三个元素，最高层级2层
插入score=30的时候，随机出了3级索引，
会把header节点第2层的指针l[2]指向该元素，同时往下1层查会把第1层的score=20的指针l[1]指向该元素，同时顺着score=20往下一层查找到score=30的插入顺序插入score=60的时候，随机出了4级索引
会把header节点第3层的指针指l[3]向该元素，同时顺着header往下1层查会把第2层score=30的节点的指针l[2]指向该元素，同时顺着score=30往下1层查会把第2层score=30的节点的指针l[1]指向该元素，同时顺着score=30往下1层查然后插入score=45的时候，随机出了3级索引
从header节点第4层查，发现score=60大于45，顺着header往下1层查查到header的l[2]层，发现45>40,ok，定位到score=30score=30的l[2]指向60，将该指针指向45，同时将45的l[2]指向score=60score=30的l[1]指向60，将该指针指向45，同时将45的l[2]指向score=60理论上最多从*header的最高层到最低层，然后链表查询
删除：
定位到元素以后，通过双向链表，获取到前驱和后继节点，直接改变指针即可时间复杂度：
跳跃表最坏的时间复杂度为O(n) （索引高度只随机出一层的时候） B+ Tree之前在 记一次生产慢sql查询的解决 和InnoDB存储引擎存储结构详解-实战篇中介绍了B+ Tree的结构，以及
首先，我们先了解下：
InnoDB是以数据页为一个存储单元，默认16kb；非叶子节点存储索引，叶子节点存储数据一个bigint的索引，在一个索引页中有878条记录,一个数据页中123条数据（数据量大小和表结构有关，我贴的是我的试验数据）默认mysql三层最多数据页有 878*878 约77万个数据页 通过innodb_space -s ibdata1 -T innodb_space/t_user_info -F 1 space-index-fseg-pages-summary 可以看到具体的层级按照我试验的表结构，三层可以容纳 77*123= 9471w条数据 当时灌了5000万条数据占磁盘7.7GB插入：
如果是数值类型，非自增插入
通过底层索引，二分查找，最多8次能定位到第2层的索引页然后在第二层索引页里，通过二分，再最多进行8次定位到第3层的数据页在数据页中通过二分查找，最多再6次定位到数据如果数据页过大，还得进行页分裂如果是自增插入，只需要在内存中缓存每层的最后节点，能O(n)定位到。
如果是字符串呢？效率会进一步退化
删除
按根据主键删除
和数值型非自增插入的查询效率一样如果中间删除数据多了，导致相邻的数据页过小，还会进行页合并的操作如果非主键，先定位到主键再回表。
时间复杂度
平均时间复杂度为O(logn) 分析 相同点（以score和数据库主键id相比） 最下面一层都是顺序的，而且是双向链表都可以通过二分查找查找数据 不同点 B+ Tree的结构是平衡的，层级默认3级，时间复杂度为O(logn)zset的跳表数据结构，最高64层，最矮就1层，每个score的对应的层级都是随机的，时间复杂度最差为O(n)跳表一个节点存储一条数据B+ Tree是以页为单位存储索引和数据隐性不同： redis是纯内存，无磁盘IOmysql是内存+磁盘 ，如果索引都在磁盘，需要3次IO，如果树的层级高了，需要的IO