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

跳表(skip list)

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

  • 查询数据的时间复杂度是 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)

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

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

B+ 树的特点:

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

mysql 索引

相关推荐