第 5 章：跳跃表

一个跳跃表示例。

digraph { rankdir = LR; node [shape = record, width = "0.5"]; // l [label = " <header> header | <tail> tail | level \n 5 | length \n 3 "]; subgraph cluster_nodes { style = invisible; header [label = " <l32> L32 | ... | <l5> L5 | <l4> L4 | <l3> L3 | <l2> L2 | <l1> L1 "]; bw_null [label = "NULL", shape = plaintext]; level_null [label = "NULL", shape = plaintext]; A [label = " <l4> L4 | <l3> L3 | <l2> L2 | <l1> L1 | <backward> BW | 1.0 | o1 "]; B [label = " <l2> L2 | <l1> L1 | <backward> BW | 2.0 | o2 "]; C [label = " <l5> L5 | <l4> L4 | <l3> L3 | <l2> L2 | <l1> L1 | <backward> BW | 3.0 | o3 "]; } subgraph cluster_nulls { style = invisible; n1 [label = "NULL", shape = plaintext]; n2 [label = "NULL", shape = plaintext]; n3 [label = "NULL", shape = plaintext]; n4 [label = "NULL", shape = plaintext]; n5 [label = "NULL", shape = plaintext]; } // l:header -> header; l:tail -> C; header:l32 -> level_null [label = "0"]; header:l5 -> C:l5 [label = "3"]; header:l4 -> A:l4 [label = "1"]; header:l3 -> A:l3 [label = "1"]; header:l2 -> A:l2 [label = "1"]; header:l1 -> A:l1 [label = "1"]; A:l4 -> C:l4 [label = "2"]; A:l3 -> C:l3 [label = "2"]; A:l2 -> B:l2 [label = "1"]; A:l1 -> B:l1 [label = "1"]; B:l2 -> C:l2 [label = "1"]; B:l1 -> C:l1 [label = "1"]; C:l5 -> n5 [label = "0"]; C:l4 -> n4 [label = "0"]; C:l3 -> n3 [label = "0"]; C:l2 -> n2 [label = "0"]; C:l1 -> n1 [label = "0"]; bw_null -> A:backward -> B:backward -> C:backward [dir = back]; label = "\n 图 5-1 一个跳跃表"; }

从跳跃表的表头向表尾进行遍历。

digraph { rankdir = LR; node [shape = record, width = "0.5"]; // l [label = " <header> header | <tail> tail | level \n 5 | length \n 3 "]; subgraph cluster_nodes { style = invisible; header [label = " <l32> L32 | ... | <l5> L5 | <l4> L4 | <l3> L3 | <l2> L2 | <l1> L1 "]; bw_null [label = "NULL", shape = plaintext]; level_null [label = "NULL", shape = plaintext]; A [label = " <l4> L4 | <l3> L3 | <l2> L2 | <l1> L1 | <backward> BW | 1.0 | o1 "]; B [label = " <l2> L2 | <l1> L1 | <backward> BW | 2.0 | o2 "]; C [label = " <l5> L5 | <l4> L4 | <l3> L3 | <l2> L2 | <l1> L1 | <backward> BW | 3.0 | o3 "]; } subgraph cluster_nulls { style = invisible; n1 [label = "NULL", shape = plaintext]; n2 [label = "NULL", shape = plaintext]; n3 [label = "NULL", shape = plaintext]; n4 [label = "NULL", shape = plaintext]; n5 [label = "NULL", shape = plaintext]; } // l:header -> header [style = dashed]; l:tail -> C; header:l32 -> level_null [label = "0"]; header:l5 -> C:l5 [label = "3"]; header:l4 -> A:l4 [label = "1", style = dashed]; header:l3 -> A:l3 [label = "1"]; header:l2 -> A:l2 [label = "1"]; header:l1 -> A:l1 [label = "1"]; A:l4 -> C:l4 [label = "2"]; A:l3 -> C:l3 [label = "2"]; A:l2 -> B:l2 [label = "1", style = dashed]; A:l1 -> B:l1 [label = "1"]; B:l2 -> C:l2 [label = "1", style = dashed]; B:l1 -> C:l1 [label = "1"]; C:l5 -> n5 [label = "0"]; C:l4 -> n4 [label = "0"]; C:l3 -> n3 [label = "0"]; C:l2 -> n2 [label = "0", style = dashed]; C:l1 -> n1 [label = "0"]; bw_null -> A:backward -> B:backward -> C:backward [dir = back]; label = "\n 图 5-3 遍历整个跳跃表"; }

从跳跃表的表尾向表头进行遍历。

digraph { rankdir = LR; node [shape = record, width = "0.5"]; // l [label = " <header> header | <tail> tail | level \n 5 | length \n 3 "]; subgraph cluster_nodes { style = invisible; header [label = " <l32> L32 | ... | <l5> L5 | <l4> L4 | <l3> L3 | <l2> L2 | <l1> L1 "]; bw_null [label = "NULL", shape = plaintext]; level_null [label = "NULL", shape = plaintext]; A [label = " <l4> L4 | <l3> L3 | <l2> L2 | <l1> L1 | <backward> BW | 1.0 | o1 "]; B [label = " <l2> L2 | <l1> L1 | <backward> BW | 2.0 | o2 "]; C [label = " <l5> L5 | <l4> L4 | <l3> L3 | <l2> L2 | <l1> L1 | <backward> BW | 3.0 | o3 "]; } subgraph cluster_nulls { style = invisible; n1 [label = "NULL", shape = plaintext]; n2 [label = "NULL", shape = plaintext]; n3 [label = "NULL", shape = plaintext]; n4 [label = "NULL", shape = plaintext]; n5 [label = "NULL", shape = plaintext]; } // l:header -> header; l:tail -> C [style = dashed]; header:l32 -> level_null [label = "0"]; header:l5 -> C:l5 [label = "3"]; header:l4 -> A:l4 [label = "1"]; header:l3 -> A:l3 [label = "1"]; header:l2 -> A:l2 [label = "1"]; header:l1 -> A:l1 [label = "1"]; A:l4 -> C:l4 [label = "2"]; A:l3 -> C:l3 [label = "2"]; A:l2 -> B:l2 [label = "1"]; A:l1 -> B:l1 [label = "1"]; B:l2 -> C:l2 [label = "1"]; B:l1 -> C:l1 [label = "1"]; C:l5 -> n5 [label = "0"]; C:l4 -> n4 [label = "0"]; C:l3 -> n3 [label = "0"]; C:l2 -> n2 [label = "0"]; C:l1 -> n1 [label = "0"]; bw_null -> A:backward -> B:backward -> C:backward [dir = back, style = dashed]; label = "\n 图 5-6 从表尾向表头方向遍历跳跃表"; }