Research indexJournal article
Write-Optimized Skip Lists
Bender, Farach-Colton, Johnson and 4 others
9 May 2017Open access
NobleIDark:/48914/w1/20260524/A8B78E41DOI10.1145/3034786.3056117
Journal articleOpen access
Write-Optimized Skip Lists
Bender, Farach-Colton, Johnson and 4 others · 2017
NobleIDark:/48914/w1/20260524/A8B78E41DOI10.1145/3034786.3056117
Abstract
The skip list is an elegant dictionary data structure that is commonly deployed in RAM. A skip list with N elements supports searches, inserts, and deletes in O(log N) operations with high probability (w.h.p.) and range queries returning K elements in O(log N + K) operations w.h.p.