Day36
学习内容 ：跳表：为什么Redis一定要用跳表来实现有序集合？
跳表是一种动态数据结构，实现灵活，可以通过改变索引构建策略，有效平衡执行效率和内存消耗、提高查询效率。
1.如何理解“跳表”？
跳表：链表加多级索引的结构。
跳表使用空间换时间的设计思路，通过构建多级索引来提高查询的效率，实现了基于链表的“二分查找”。
2.用跳表查询到底有多快？
跳表是一种动态数据结构，支持快速的插入、删除、查找操作，时间复杂度都是 O(logn)。
理解公式推导过程：
第 k 级索引的结点个数是第 k-1 级索引的结点个数的 1/2，那第 k级索引结点的个数就是 n/(2k)。
假设索引有 h 级，最高级的索引有 2 个结点。通过上面的公式，我们可以得到 n/(2h)=2，从而求得 h=log2n-1。
3.跳表是不是很浪费内存？
看是否浪费内存，看空间复杂度。
比起单纯的单链表，跳表需要存储多级索引，肯定要消耗更多的存储空间。
跳表的空间复杂度是 O(n)。不过，跳表的实现非常灵活，可以通过改变索引构建策略，有效平衡执行效率和内存消耗。
4.如何高效的动态插入和删除？
跳表这个动态数据结构，不仅支持查找操作，还支持动态的插入、删除操作，而且插入、删除操作的时间复杂度也是 O(logn)。
5.跳表索引如何动态更新？
跳表是通过随机函数来维护前面提到的“平衡性”。
我们通过一个随机函数，来决定将这个结点插入到哪几级索引中，比如随机函数生成了值 K，那我们就将这个结点添加到第一级到第 K 级这 K 级索引中。
最好自己代码再实现一遍“跳表”，加深理解。
本文参考【极客时间】专栏《数据结构与算法之美》。
网友评论