知识卡片
跳表更新保存各层前驱
跳表从高层向低层寻找key,沿途记录每层最后一个小于目标的前驱。插入时随机选层数,再改这些前驱的forward;已有key则更新值。删除同样按前驱数组跳过目标,最高空层回缩。原伪码中level与lvl等记号不完全统一,应按新节点实际层数理解,不直接照抄编译。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 大数据常用的算法与数据结构 · 查看原书依据
上述算法中update数组用于临时存放查找searchKey路径时每层最后的节点,主要目的是记录信息,使得在插入节点时能像普通链表插入时一样修改新插入节点导致的各种指针变化。SkipList的插入算法整体逻辑也很清楚:首先与查找算法一样找到searchKey应该插入的位置,在查找过程中往update数组中记录查找路径每层最后的节点;如果找到相同key的节点,则只需更新其值即可,否则利用随机数确定新插入节点的层级,如果新节点层级数比目前链表中的MaxLevel要高,那么需要更新链表表头的层级指针信息并重设MaxLevel数值,然后生成新节点并插入链表,并根据update数组保留的信息调整各个层级的相关指针指向。
参考来源
- 位置:《大数据日知录:架构与算法》第3章《大数据常用的算法与数据结构》(来源项目:book-sources;源文件:extracted/大数据日知录_架构与算法/_epub-src/OEBPS/text00008.html)
- 结论依据:原文以“update数组用于临时存放”所在段落解释具体机制;本卡保留其条件,另将实现限制、勘误和教学推导在正文中明确区分。
- 原始内容:上述算法中update数组用于临时存放查找searchKey路径时每层最后的节点,主要目的是记录信息,使得在插入节点时能像普通链表插入时一样修改新插入节点导致的各种指针变化。SkipList的插入算法整体逻辑也很清楚:首先与查找算法一样找到searchKey应该插入的位置,在查找过程中往update数组中记录查找路径每层最后的节点;如果找到相同key的节点,则只需更新其值即可,否则利用随机数确定新插入节点的层级,如果新节点层级数比目前链表中的MaxLevel要高,那么需要更新链表表头的层级指针信息并重设MaxLevel数值,然后生成新节点并插入链表,并根据update数组保留的信息调整各个层级的相关指针指向。
- 边界对照:[LevelDB实现说明](https://raw.githubusercontent.com/google/leveldb/main/doc/impl.md)、[Bitcoin原论文](https://bitcoin.org/bitcoin.pdf)、[SILT原论文](https://www.cs.cmu.edu/~dga/papers/silt-sosp2011.pdf);用于校正原书简化,未将书外观点伪作原文。