Redis-skip表的底层数据结构
Skiplist是一种有序的数据结构，通过维护指向每个节点中其他节点的多个指针，可以快速访问节点。具有以下属性：
1.它由许多层组成；
2.每层是一个有序链表，从上到下排列，包含至少两个链表节点，即前头节点和后零节点；
3.最低的链表包含所有元素；
4.如果某个元素出现在某一层的链表中，该层下的所有链表也会出现(上一层的元素是当前层元素的子集)；
5.链表中的每个节点包含两个指针，一个指向同一层中的下一个链表节点，另一个指向下一层中的同一链表节点；
Redis中的跳转表节点定义如下：
typedef结构zskiplistNode {
//图层
struct zskiplistLevel {
//正向指针
结构zskiplistNode *向前；
//span
无符号整数跨度；
}级别[]；
//后指针
向后构造zskiplistNode *；
//分数
双重评分；
//成员对象
robj * obj
} zskiplistNode
多个跳转表节点形成跳转表：
typedef结构zskiplist{
//页眉节点和页脚节点
structz skiplistNode *头，*尾；
//表中的节点数
无符号长长度；
//表格中层数最多的节点的层数
int级别；
} zskiplist
(1)搜索：从顶层链表节点开始，如果比当前节点大，比当前级别的下一个节点小，那么向下看，也就是和当前级别的下一级节点的下一个节点进行比较，以此类推，直到找到底部的最后一个节点，如果找到，就返回，否则为空。
插入：首先确定要插入的层数。一种方法是假设抛硬币。如果是正的，就会累积，直到遇到负的一面。最后，记录正边数作为要插入的层数。当插入层数k确定后，需要从底层向k层插入新元素。
删除：在每个图层中找到包含指定值的节点，然后从链表中删除该节点。如果删除后只剩下两个节点，则删除该层。
内容来源网络，如有侵权，联系删除，本文地址：https://www.230890.com/zhan/81987.html