Redis学习笔记-跳表

跳表的数据结构介绍

Redis中使用跳表(Skip List)作为有序集合(Sorted Set)的底层数据结构。

跳表是一种基于链表的数据结构，它通过在每一层链表中添加额外的指针，以快速跳过部分元素，从而提高查找效率。

在Redis中，有序集合使用跳表来实现，其中每个元素都有一个对应的分值score(key)和成员值member(value)。

跳表按照分值(key)进行排序(要求链表key值有序)，可以快速根据分值范围或者成员值查找元素。

1. 跳表的数据结构

会结合这张图，进行详细的分析：

首先是每个结点的数据结构：

  
template<typename K,typename V>
class Node{
public:
    Node(){}
    Node(K k, V v, int);
    ~Node();
    // ...
    Node <K,V> **forward; // 该指针指向存储每层跳表节点节点的数组，数组大小取决于所在层，也就是说是一个指向数组(数组名本身也是指针)的指针
    int node_level;       // 节点所在层
private:
     K key;
     V value;
};

为什么每个结点都附带一个指向存储链表结点地址的数组的指针呢？

类比单链表，链表中每个结点都会附带一个指向下一个结点地址位置的指针；
而在跳表的数据结构里，每个结点同样需要附带一个指向下一个位置的指针，只不过由于多层索引的数据结构，结点需要存储的不仅仅是单个结点的地址，而是要存储它下一个结点在每一个索引层的地址；
因此forward指向了一个数组地址值；

跳表的相关操作

首先观察每个跳表结点的构造函数，深刻理解其中各个数据的实际意义；

跳表结点的构造函数

上代码：

  
template<typename K,typename V>
Node<K,V>::Node(const K k, const V v, int level)
{
    this->key = k;              // 键值
    this->value = v;            // 值
    this->node_level = level;   // 当前层级
    this->forward = new Node<K,V> *[level + 1]; // 分配一个元素类型为指向Node节点指针的数组，forward指向该数组
    memset(this->forward, 0, sizeof(Node<K,V>*) * (level + 1));   // 将这段数组空间地址中的内容全赋为0
};

了解了跳表节点的构造过程，接下来看看如何搭建起整个跳表数据结构的框架：

首先应该聚焦的是最底层的那个结点，我们预先简单认为这是一张普通的单链表；
与普通单链表结点不同的是，该单链表中某些结点，会被作为跳表中其他层的索引，也就是说，这个点在跳表中存在多个，而这些多出来的个数都作为了索引；
- 比如图片中存储1: 数据结构、3: 操作系统、5: 数据库的结点；
但是并非每个结点都会被做索引，有些结点可能只存在于最底层；
- 比如图片中存储2: 计算机网络、4: 组成原理、6: 编译原理的结点；

基于上面的分析，我们再结合原图，可以将每个结点进行标注：

2. 标注版

需要注意的几个细节问题：

跳表中每个结点所存储的指针是一个数组，数组的长度等于跳表的层数；
为什么叫跳表，就是我们只要指定了某一层，比如index层，我们能根据这个信息快速定位到我们要找到的结点；

接下来，我们针对图片中内容做一些修改，详细展示跳表的插入流程；

跳表中结点的插入

我们对之前的跳表略加修改，以便展示跳表中节点的插入过程：

我们接下来要插入2: 计算机网络、4: 组成原理、6: 编译原理三个课程节点，且看我们应该怎么做：

插入节点2: 计算机网络；

基于最底层的链表节点开始，我们依次开始从最高层判断节点的key值与2的大小比较结果；
显然，最高层第一个节点1比2小，更新到下一个结点，我们发现在这一层该节点指向的下一个结点的值为5，比2大，将该节点存入到一个指针数组update[i]当中；
然后，下一层，从上一个存储的结点开始，又遍历，发现在这一层该节点指向的下一个结点的值为3，比2大，又将这一层的这个节点存入到update[i-1]当中；
再继续，从上一个存储的结点1开始，又遍历，发现在这一层该节点指向的下一个结点的也是3，比2大，又将这一层的这个节点存入到update[i-2]当中；

经过这些步骤，我们成功找到了要插入的结点的前一个位置，接下来就是要针对每一层进行元素的插入了：

首先生成这么一个结点：Node<K,V>* inserted_node = create_node(key, value, random_level);
random_level结点参数后续会介绍，先不管，生成结点之后，针对update数组中保存的每一层插入位置处的前一个结点，我们进行插入，即可；

最终得到这一个图：

虽然图片中是只在最底层插入了，但其实其他层同样有可能插入该图片，我们我们采取的是一个随机策略，随机策略的主代码：

  
 /**
 * @brief 生成一个随机层级，从第一层开始，每一层以50%的概率加入；
 * @return 返回一个随机的层级；
 */
 template<typename K,typename V>
 int SkipList<K,V>::get_random_level()
 {
     int k = 1;
     while(rand() % 2)   // 生成一个随机整数，奇数则增
     {
         ++k;
     }
     k = (k<_max_level) ? k : _max_level;    // 但不能无限增长，需要用max_level限制
     return k;
 };

我们假定上面生成的一个随机整数是1，也就是在最底层插入，这个好理解，最底层的索引是0，0下标正好对应数组只有一个元素；

依样画瓢，我们再插入一个4结点4: 组成原理
- 基于最底层的链表节点开始，我们依次开始从最高层判断节点的key值与4的大小比较结果；
- 显然，最高层第一个节点1比4小，然后更新该层的下一个节点，我们发现在这一层该节点指向的下一个结点的值为5，比4大，将该节点存入到一个指针数组update[i]当中；
- 然后，下一层，从上一个存储的结点开始，又遍历，发现在这一层该节点指向的下一个结点的值为3，比4小，继续遍历，到3这个结点，发现这个结点的下一个结点值5比4大，于是将这一层的这个节点3存入到update[i-1]当中；
- 再继续，从上一个存储的结点3开始，又遍历，发现在这一层该节点指向的下一个结点是5，比4大，又将这一层的这个节点3存入到update[i-2]当中；
- 于是update数组中获得了3个结点的指针地址：1: 数据结构、3: 操作系统、3: 操作系统；
继续同上步骤插入即可，最终得到图片；

通过上面两个结点插入的示例，我们基本对整个跳表的结构了然于心了，从代码实现上来看，插入结点的核心代码主要分为这么几部分：

寻找要插入结点的位置处的前一个结点：

  
// 从当前列表层级开始，逐步向下，从这里可以看到的是，每层的索引都会被更新
for(int i = _skip_list_level; i >= 0; --i)
{
    // 只要该层链表头结点不为空，同时该层头结点的key要小于要插入的key
    // 从这里可以看到，key要求有序
    while(current->forward[i] && current->forward[i]->get_key() < key)
    {
        // current更新为该节点在第i层的下一个节点，直到他指向的下一个结点大于要插入的key
        current = current->forward[i];
    }
    // update是存储每一层(包括索引层)需要插入节点的位置，因为每层都需要更新(每层的结点都是一致的)；
    update[i] = current;
}

通过一个随机函数确定要插入结点的层；
- 如果生成的随机层数超出了当前最高层，那么需要为多出来的层进行初始化，初始化主要体现在update数组的更新；
- 但与之伴随的一个细节是，生成的结点层数发生了变化，变多了，这就意味着，即将要插入的那个结点中的指针指向的数组长度也变大了；
- 但这与结点有关吗？无关，因为，每个结点存储的仅仅是一个指针数组而言，无非是后续的层数变多了；
定位了要插入的位置后，每层依次插入元素；
再有的一个细节是，如果遇到key相同的结点，表明节点已存在，那么插入就没必要进行了；

从这里大致上也可以看出时间复杂度了，复杂度主要体现在层数上，需要一层一层查找合适的节点，但是每层查找的时间复杂度为1，时间复杂符取决于层数；层数的复杂度为对数级别；

跳表中结点的查找

经过对结点插入的一系列分析，对查找的分析更是了然于胸了；

直接附上核心代码：

  
for(int i = _skip_list_level; i >= 0 ; --i) // 从最底层索引开始
{
    while(current->forward[i] && current->forward[i]->get_key() < key)
    {
        current = current->forward[i];
    }
}
// 更新current到最底层链表的结点，这个结点如果找到了对应值那就是结点了
current = current->forward[0];
if(current && current->get_key() == key )
{
    std::cout << "Found key:" << key <<", value:" << current->get_value() << std::endl;
    return true;
}
std::cout<<"Not Found Key: "<< key << std::endl;

跳表中结点的删除

删除结点是插入节点的逆过程，将每一层中等于该键值的结点删除；

但是需要注意到一些细节问题，接下来会一一说到；

删除步骤：

首先还是要定位到结点，对于存在该结点值的层，我们找到该结点的前一个结点，存入数组update[i]，对于不存在该结点的层，我们也找到小于该节点的最大结点；

核心代码：

  
 for(int i = _skip_list_level; i >= 0; --i)
 {
     while(current->forward[i] && current->forward[i]->get_key() < key)
     {
         current = current->forward[i];  // 不断循环，定位到要删除的结点
     }
     // 每一层要删除的结点保存在数组中
     // 如果找到了目标结点，这里保存的是目标结点的前一个结点
     // 如果没找到目标结点，该节点要么保存的是最后一个结点，要么是小于那个结点值的最大值
     update[i] = current;
 }

 current = current->forward[0];  // 指向底层的相应结点

做删除处理；

有两个细节，首先是我们需要意识到并非每层都会有索引值，这部分是需要考虑到的细节；
其次是，有些层经过处理之后已经为空，为空的索引层可以删除掉；

代码：

  
 if(current && current->get_key() == key)
 {
     for (int i = 0; i <= _skip_list_level; ++i) {
         // 由于某些键值并不一定存在于某层，因此这种情况
         if (update[i]->forward[i] != current) {
             std::cout << "The key isn't exist in level " << i << ";" << std::endl;
             // 使用break是因为，如果这一层都不存在该索引，显然往上更不可能存在
             // 因为每一层的值都来源于上一层，如果下一层某个值不存在，那么往上更不可能存在；
             break;
         }
         // 中间的结点值不需要delete吗，不需要，因为Node结点已经自行设定了析构函数
         update[i]->forward[i] = current->forward[i];
     }
     // 删除空层(从上到下依次删)
     while(_skip_list_level > 0 && _header->forward[_skip_list_level] == nullptr)
     {
         --_skip_list_level;
     }
     std::cout<<"Successfully deleted key" << key <<std::endl;
     --_element_count;
 }

以上就是关于跳表数据结构的详细介绍，跳表的设计真的太精妙了！