Redis 跳表（skip list) 与 mysql 索引 B+tree

跳表（skip list）

• 查询数据的时间复杂度是 O(logN)
• 插入操作的时间复杂度是 O(logN)
• 删除操作的时间复杂度是 O(logN)
• 空间复杂度 O(N)

Redis zset（有序集合）

Reids 有序集合支持的核心操作有：插入数据、查找数据、删除数据以及根据 score 按照区间查找数据，跳表对应操作的时间复杂度都可以很好的满足这些要求。

Redis 有序集合的底层编码有两种实现，分别是 ziplist 和 skiplist
当有序集合的元素个数小于 zset-max-ziplist-entries 配置（默认128个），并且每个元素的值都小于 zset-max-ziplist-value 配置（默认64字节）时，Redis 会用 ziplist 来作为有序集合的内部实现，上述两个条件之一不满足时，Redis 启用 skiplist 作为有序集合内部实现。

B+ 树（B+tree）

• 查询数据的时间复杂度是 O(logN)
• 插入操作的时间复杂度是 O(logN)
• 删除操作的时间复杂度是 O(logN)
• 空间复杂度 O(N)

B+ 树的特点：

• 每个节点中子节点个数不超过 m，也不能少于 m/2
• m 叉树非叶子节点其只存储索引，不存储数据
• 列表项目
• 列表项目

mysql 索引