第 5 章《跳跃表》勘误

40 页

这一页的 5.1.1 节展示 zskiplistNode 结构的定义时, 作者错误地将 level[] 属性放到了 zskiplistNode 定义的最前面, 但是因为 level[] 属性是动态数组, 所以它不能被放在 backwardscore 等属性的前面, 原文是错误的。

以下是修正之后的 zskiplistNode 结构的定义:

typedef struct zskiplistNode {

    // 后退指针
    struct zskiplistNode *backward;

    // 分值
    double score;

    // 成员对象
    robj *obj;

    // 层
    struct zskiplistLevel {

        // 前进指针
        struct zskiplistNode *forward;

        // 跨度
        unsigned int span;

    } level[];

} zskiplistNode;

感谢 程辙 反馈这个错误。

43 页

图 5-6 中, header 属性连接表头节点的连线应该是实线而不是虚线, 以下是修正后的图片:

../_images/5-6.svg

45 页

表 5-1 中对 zslIsInRange 函数的描述有误, 以下是修正后的描述:

函数

作用

时间复杂度

zslIsInRange

给定一个分值范围(range), 比如 0152028 ,诸如此类, 如果给定的分值范围包含在跳跃表的分值范围之内, 那么返回 1 ,否则返回 0

通过跳跃表的表头节点和表尾节点, 这个检测可以用 O(1) 复杂度完成。

感谢 IwfWcf 反馈这个错误。