BlogGitHub

《Redis 设计与实现》笔记 - 跳跃表

Java 中的跳跃表 - ConcurrentSkipListMap

数据结构

/**
 * Nodes hold keys and values, and are singly linked in sorted
 * order, possibly with some intervening marker nodes. The list is
 * headed by a header node accessible as head.node. Headers and
 * marker nodes have null keys. The val field (but currently not
 * the key field) is nulled out upon deletion.
 */
static final class Index<K,V> {
    final Node<K,V> node;  // currently, never detached
    final Index<K,V> down;
    Index<K,V> right;
    Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {
        this.node = node;
        this.down = down;
        this.right = right;
    }
}

/**
 * Index nodes represent the levels of the skip list.
 */
static final class Node<K,V> {
    final K key; // currently, never detached
    V val;
    Node<K,V> next;
    Node(K key, V value, Node<K,V> next) {
        this.key = key;
        this.val = value;
        this.next = next;
    }
}

Redis 中的跳跃表

数据结构

zskiplistNoe

字段描述：

  1. zskiplistNode 的 level 数组可以包含多个元素，每个元素都包含一个指向其它节点的指针；

    1. zskiplistLevel 每层都有一个指向表尾方向的指针（level[i].forward），用于从表头向表尾访问节点；

    2. zskiplistLevel 每层都有一个跨度（level[i].span），用于记录两个节点之间的距离；

  2. zskiplistNode 的 backward 属性用于从表尾向表头方向访问节点，但每次只能后退一个节点；

  3. zskiplistNode 的 score 属性是一个 double 类型的浮点数，跳跃表中的所有节点都按分值的从小到大来排序；

  4. zskiplistNode 的 obj 属性是一个指向字符串对象的指针，字符串对象保存着一个 SDS 值。

zskiplistlist

最后更新于