Redis 的跳表（skiplist）用于实现有序集合（sorted sets）等功能，其中跳表索引的建立是通过动态层级（levels）和前进指针（forward pointers）实现的。

跳表索引的建立过程既简单又高效，允许快速访问跳表中的元素。

跳表索引是如何建立的：

基本概念

  1. 节点（Node）：每个节点保存了跳表的一个元素，包括其分数（score）和成员（member）。
  2. 层级（Level）：跳表由多个层级组成，底层包含所有元素。每一层是上一层的子集，顶层层级拥有最少的元素。
  3. 前进指针（Forward Pointers）：每个节点包含一组指针，指向同一层级的下一个节点。

索引建立过程

  1. 初始化：创建跳表时，它包含一个特殊的头节点（head），头节点的层级为跳表的最大层级。初始时，所有层级的前进指针都指向 NULL。

  2. 插入元素：
    • 随机层级：为每个新插入的元素随机生成一个层级数，这个数决定了新节点将存在于跳表的哪些层级中。随机层级有助于保持跳表的平衡性。层级数通常是通过一个随机过程确定的，例如抛硬币头朝上连续出现的次数。
    • 层级更新：从跳表的最高层开始，搜索应该插入新节点的位置。对于每一层，如果下一个节点的分数大于要插入的节点的分数，或者下一个节点是 NULL，那么就在当前层插入新节点，并且更新当前层的指针，以指向新插入的节点。然后，继续在下一层重复这一过程，直到达到新节点的随机层级。
    • 指针调整：对于新节点的每一层，都需要调整该层前一个节点的前进指针，使之指向新节点，同时将新节点的前进指针指向原来前一个节点指向的节点。
  3. 删除元素（涉及到索引的更新）：
    • 遍历每一层，寻找要删除的元素。
    • 对于找到元素的每一层，更新前一个节点的前进指针，绕过要删除的节点，直接指向要删除节点的下一个节点。
  4. 搜索：
    • 从头节点的最高层开始，逐层向下搜索，直到找到目标元素或达到底层。
    • 在每一层，如果下一个节点的分数小于或等于目标分数，则向前移动到下一个节点；如果大于目标分数，或到达了当前层的末尾（NULL），则向下移动到下一层继续搜索。

通过这种方式，跳表能够在对数时间内完成插入、删除和搜索操作，同时保持元素的有序性。

跳表的这种索引建立方式使其成为实现 Redis 有序集合的理想选择，既保证了操作效率，也简化了实现复杂度。