高级数据结构-SE2322

前言：
不是我的专业课，是SE好友的专业课，好奇故浅尝一下。

Lec1 Skiplist

• An element NIL is allocated and given a key greater than any legal key.
• All levels of all skip lists are terminated with NIL.
• A new list is initialized so that the level of the list is equal to 1 and all forward pointers of the list’s header point to NIL

• 查找：由粗到细 = 由高到低

• 分层次，相互耦合的多列表： $S_0, … S_h$
• 顶层$S_0$ 底层$S_h$
• 每个节点最多拥有4个引用
  • 横向为层level：prev(), next() （头尾哨兵）
  • 纵向称塔tower：above(), below()

• LSM算法
• LSM模型利用批量写入解决了随机写入的问题，虽然牺牲了部分读的性能，但是大大提高了写的性能。