Why Are Skip Lists Less Commonly Used Than BSTs?

Skip lists are a data structure that can serve as an alternative to binary search trees (BSTs). While they are simple in concept and easy to implement, they are not as widely adopted as BSTs. Curious about the reasons behind this, I decided to investigate.

Features of Skip Lists

Skip lists are an extension of linked lists, designed to provide tree-like performance. Below is a simple example of their structure:

Level 3: A ------> C ----------------> Z
Level 2: A ------> C ------> X ------> Z
Level 1: A -> B -> C -> M -> X -> Y -> Z

Features

• Hierarchical Structure:

  • The bottom level is a standard sorted linked list.
  • The upper levels link only some nodes, allowing the search to skip over lower levels.
  • The topmost level contains only a minimal number of nodes (e.g., the head and tail of the list).

• Efficiency:

  • The expected time complexity for search, insertion, and deletion is O(log n).

• Simplicity:

  • Skip lists are relatively easy to implement and more intuitive to understand than balanced trees.

For those interested in more details, including implementation, I recommend reading Advanced Data Structures Series— Skip List, which provides a clear and comprehensive explanation.

Why Are BSTs More Popular?

BSTs, especially balanced BSTs, are more commonly used than skip lists for several practical and technical reasons. Comparing the two reveals key factors that favor BSTs.

Upon investigation, it was found that BSTs were introduced in 1960, while skip lists were invented in 1989 by William Pugh. This 30-year difference has allowed BSTs to mature significantly, with broader support in standard libraries and more robust implementations.

Feature	BST	Skip List
Time Complexity	✅	-
Memory Efficiency	✅	-
Robustness	✅	-
Query Flexibility	✅	-
Parallel Processing	-	✅

Guarantee of Time Complexity

Skip lists are efficient with an expected time complexity of O(log n) for search, insertion, and deletion. However, since they rely on randomness, their worst-case time complexity can degrade to O(n). In contrast, balanced BSTs perform rebalancing after every insertion or deletion, ensuring a worst-case time complexity of O(log n). This stability is particularly important in practical applications where performance guarantees are required. As a result, balanced BSTs are often preferred in scenarios where consistent performance is critical.

Memory Efficiency

Skip lists require multiple pointers per node to create their hierarchical structure, resulting in higher memory consumption. In comparison, BSTs only require two pointers per node (left and right), making them significantly more memory-efficient. When memory usage needs to be minimized or memory efficiency is a priority, BSTs are the more suitable choice.

Robustness

Skip lists rely on randomness for hierarchical division, which results in a structure that can vary between executions. While this randomness provides simplicity and efficiency, it can also lead to performance variability. On the other hand, balanced BSTs have a deterministic structure, ensuring that the same operations on the same data always yield identical results. This predictability enhances the reliability and stability of the system, making balanced BSTs particularly valuable in scenarios where robustness is critical.

Query Flexibility

Balanced BSTs offer a wide range of advanced query operations based on order, such as finding the minimum and maximum values, ordered traversal, and range queries. In contrast, skip lists are relatively limited in their query flexibility. While they handle specific range queries efficiently, they lack the versatility needed for more complex query requirements. As a result, balanced BSTs are a better fit for applications requiring sophisticated query capabilities.

Parallel Processing Support

Skip lists are well-suited for parallel processing because each node operates independently within the linked structure. In contrast, BSTs require rebalancing of the entire tree, making parallel processing more challenging. As a result, skip lists often have an advantage in scenarios where parallelism is crucial.

Conclusion

Skip lists are a convenient data structure known for their simplicity, ease of implementation, and efficiency in performing search, insertion, and deletion operations. They are particularly useful in systems like Redis, an in-memory database, and other speed-critical applications. However, balanced BSTs are more commonly adopted due to the following reasons:

1. Guarantee of Time Complexity (Worst-case O(log n))
2. High Memory Efficiency
3. Predictable Behavior Independent of Randomness
4. Rich Query Flexibility

Subjectively, the relationship between BSTs and Skip Lists feels like "a professional full-course meal vs. a family’s go-to dish." BSTs involve meticulous cost management and fine-tuning to consistently deliver perfect results. On the other hand, Skip Lists are akin to a simple recipe with an easy process, capable of quickly delivering a solid 80+ points with minimal effort.

From a practical perspective, the extent to which one can tolerate the variability caused by randomness may require negotiation with the business side. However, Skip Lists are worth considering as a viable alternative depending on the scenario.

References

• Skip List (Wikipedia)
• Binary Search Tree (Wikipedia)
• Key Algorithms and Data Structures (IEICE) *JAPANESE
• Skip Lists Lecture Notes (ICS UCI)
• Advanced Data Structures Series— Skip List (Medium)