cockroachdb / cockroachdb/pebble
arenaskl: consider alternative TrySeekingUsingNext optimizations
- Dominant language
- Go
- Stars
- 6k
- Forks
- 584
- Avg merge
- 16h 35m
- Merged PRs (30d)
- 5
Description
The arenaskl Iterator implementation implements the TrySeekUsingNext optimization through performing simple Nexts:
https://github.com/cockroachdb/pebble/blob/6c6fd7553fc59a1223ff0289f3c02164c23d442e/internal/arenaskl/iterator.go#L94-L115
If it doesn't find the sought key within 5 nexts, it abandons the work it's already done and starts anew. We could instead take advantage of the skiplist node structure and try advancing at levels above the base level but below the list height.
I'm imagining something like:
```
Initialize level = 0
for range 5 {
next := n.tower[level]
if key <= next.key {
return searchDescending(next, level, key)
}
n = next
if n.height > level+1 {
level++
}
}
```
Jira issue: PEBBLE-1197
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.