聊聊 Mysql 索引和 redis 跳表

比眉伴天荒 2021-09-21 06:08 376阅读 0赞

### 一、Redis中的跳表 ###

跳表可以简单理解就是给链表加索引，当结点数量多的时候，这种添加索引的方式，会使查询效率提高的非常明显。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70]

跳表这个动态数据结构，不仅支持查找操作，还支持动态的插入、删除操作，而且插入、删除操作的时间复杂度也是 ○(㏒n)。

对于单纯的单链表，需要遍历每个结点来找到插入的位置。但是对于跳表来说，因为其查找某个结点的时间复杂度是 ○(㏒n)，所以这里查找某个数据应该插入的位置，时间复杂度也是 ○(㏒n)。

--------------------

### 二、数据库中的 B 树和 B + 树 ###

1.B 树，每个节点都存储 key 和 data，所有节点组成这棵树，并且叶子节点指针为 null，叶子结点不包含任何关键字信息。

2.B + 树，所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接，所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。(而 B 树的非终节点也包含需要查找的有效信息)

*  非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。
 *  树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录。

3.B 和 B + 树的区别在于，B + 树的非叶子结点只包含导航信息，不包含实际的值，所有的叶子结点和相连的节点使用链表相连，便于区间查找和遍历。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70 1]

B+树的优势：

**1.B + 的磁盘读写代价更低**

*  B + 的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对 B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。数据存放的更加紧密，具有更好的空间局部性。一次性读入内存中的需要查找的关键字也就越多。因此访问叶子节点上关联的数据也具有更好的缓存命中率。相对来说 IO 读写次数也就降低了。

**2.B+tree 的查询效率更加稳定**

*  由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

**3. 便于区间查找**

*  B + 树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而 B 树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有 B + 树好。

--------------------

### Redis选中跳表而不使用B+树 ###

redis 使用跳表不用 B + 数的原因是：redis 是内存数据库，而 B + 树纯粹是为了 mysql 这种 IO 数据库准备的。B + 树的每个节点的数量都是一个 mysql 分区页的大小

Redis 中的有序集合是通过跳表来实现的，严格点讲，还用到了散列表（关于散列表），如果查看 Redis 开发手册，会发现 Redis 中的有序集合支持的核心操作主要有下面这几个：

*  插入一个数据
 *  删除一个数据
 *  查找一个数据
 *  按照区间查找数据（比如查找在 \[100,356\] 之间的数据）
 *  迭代输出有序序列

其中，插入、查找、删除以及迭代输出有序序列这几个操作，红黑树也能完成，时间复杂度和跳表是一样的，但是，**按照区间来查找数据这个操作，红黑树的效率没有跳表高。**

**对于按照区间查找数据这个操作，跳表可以做到 ○(㏒n) 的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了**。这样做非常高效。

当然，还有其他原因，比如，**跳表代码更容易实现，可读性好不易出错**。跳表更加灵活，可以通过**改变索引构建策略，有效平衡执行效率和内存消耗**。

--------------------

参考：https://www.cnblogs.com/aspirant/p/11475295.html

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70]: /images/20210920/d488c9867e9b4ee1808c6849d5fa4fe6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70 1]: /images/20210920/49a810fa0d3047dea17e86f9238f28fd.png