Databases Reference
In-Depth Information
Jump Pointers
1
01234
2
5
10
01234
01234
01234
Jump Pointers
Jump Pointers
Jump Pointers
7
15
01234
Jump Pointers
01234
Jump Pointers
(a) Binary Jump Index
Block 0
Jump Pointers
1
2
57
Jump Pointers
Block 1
15
19
810
21
22
25
Block 2
(b) Block-structured Jump Index
Fig. 5.
(a) Simple jump index. Shaded pointers that are not filled in are null. Only
the first five pointers in each node are shown. (b) Block-structured jump index. Only
pointers with
i
≤
4 are shown.
To address this problem, researchers have proposed
jump indexes
[20].
Jump indexes can be used to index monotonic sequences, such as document
IDs in a posting list, as a replacement for the non-trustworthy B+ trees.
Experiments show that overall, jump index lookup performance is within a
factor of 1.4 of the performance of an equivalent B+ tree.
A jump index exploits the fact that to reach a particular number
k
N
,
we can jump from 0 to
k
in powers of 2. For example, let
b
1
,...,b
p
be the
binary representation of
k
. We can reach
k
in
p
steps by starting at zero, then
jumping forward by
b
1
×
≤
2
p−
1
2
p−
2
integers, then jumping forward by
b
2
×
2
0
jump brings us to the number
k
. In a jump index, of course, not all possible numbers (record IDs) will be
stored in the index. Instead, as shown in Figure 5(a), a jump index node
contains explicit jump pointers that correspond to the sequence of jumps to
take forward. More precisely, the
i
th jump pointer stored with jump index
integers; and so on, until finally a
b
p
×
