Why DragonflyDB Uses B+ Trees for Sorted Sets Instead of Skiplists Like Redis

DragonflyDB, a Redis-compatible in-memory data store, boasts significantly higher throughput and memory efficiency. One key architectural decision contributing to this performance advantage is its choice of data structure for implementing Sorted Sets. While Redis traditionally uses Skip Lists, DragonflyDB leverages B+ Trees, achieving a reported 40% improvement in memory usage and a 500% increase in throughput. This article delves into the technical reasons behind this difference, comparing the two approaches.

Understanding Redis Sorted Sets

A Sorted Set is a widely used data structure in Redis, crucial for applications requiring ordered, unique elements, such as leaderboards or priority queues. Each member in a Sorted Set is unique and associated with a numerical score. Elements are always retrieved in ascending order based on their scores.

Redis’s Implementation: Skip List

For Sorted Sets with more than 128 elements, Redis employs a Skip List. For smaller sets (less than or equal to 128 elements), it uses a listpack, which is optimized for compact storage. Our focus here is on the Skip List.

A Skip List is a probabilistic data structure that allows for O(log N) average-case time complexity for search, insertion, and deletion operations, similar to balanced binary search trees, but with simpler implementation.

How a Skip List Works:

1. Bottom Layer: The lowest layer of a Skip List is a simple sorted doubly linked list containing all elements.
2. Express Lanes: Above the bottom layer, additional “express lanes” are built. Each successive layer typically contains approximately half the number of elements of the layer below it. These upper layers act as “expressways” to speed up traversal.
3. Search Process: To find an element, the search begins at the topmost layer. The algorithm traverses horizontally until it finds an element greater than or equal to the target. If the current element is greater, it drops down to the next lower layer and continues the search from the previous node. This process continues until the target element is found or its absence is confirmed in the bottom layer.

Overhead of Redis’s Skip List

While efficient, the Skip List implementation in Redis incurs a certain memory overhead per node. Each zskiplistNode in Redis stores:

• Member: 8 bytes
• Score: 8 bytes
• Total Essential Data: 16 bytes

Beyond this essential data, the Skip List structure adds overhead for pointers and metadata. Based on Redis’s source code and observed benchmarks, this overhead includes:

• Backward pointer
• Forward pointers (one for each level)
• Span (distance to the next node at the current level)
• Level information

Benchmarking reveals that the average overhead for a Skip List node in Redis is approximately 37 bytes. This means that for every 16 bytes of actual data (member + score), an additional 37 bytes are consumed by the data structure itself.

DragonflyDB’s Implementation: B+ Tree

DragonflyDB takes a different approach, implementing Sorted Sets using B+ Trees. This choice is a significant factor in its memory and throughput improvements.

How a B+ Tree Works

A B+ Tree is a self-balancing tree data structure that maintains sorted data and allows for efficient insertions, deletions, and searches. Key characteristics include:

• High Branching Factor: Unlike binary trees, B+ Trees can have a large number of children per node, reducing the tree’s height and thus the number of disk I/Os (or memory accesses) required for operations.
• Data in Leaf Nodes: All actual data (key-value pairs) is stored exclusively in the leaf nodes. Inner nodes only contain keys used for navigation.
• Linked Leaf Nodes: All leaf nodes are linked together in a sequential manner, forming a sorted linked list. This allows for efficient range queries.

Overhead of DragonflyDB’s B+ Tree

DragonflyDB’s B+ Tree implementation is optimized for memory efficiency. Each node in their B+ Tree is designed as a fixed-size 256-byte array.

Let’s calculate the memory usage:

• Essential Entry Size: Member (8 bytes) + Score (8 bytes) = 16 bytes per entry.
• Entries per Leaf Node: A 256-byte leaf node can store 256 bytes / 16 bytes/entry = 16 entries.

Consider a scenario with 1,000 entries:

• Number of Leaf Nodes: 1,000 entries / 16 entries/node = 62.5, so roughly 67 leaf nodes (as mentioned in the video, accounting for potential internal padding or overhead).
• Inner Nodes: With a typical branching factor of 7 to 15, a small number of inner nodes (e.g., around 10) would be required to manage these leaf nodes.
• Total Nodes: Approximately 77 nodes (67 leaf + 10 inner).

Now, let’s calculate the per-key overhead:

• Total Memory for 1,000 entries: 77 nodes * 256 bytes/node = 19,712 bytes.
• Per-Key Value Storage: 19,712 bytes / 1,000 entries = 19.712 bytes/entry.
• Actual Overhead per Entry: Since 16 bytes are for the essential member and score, the overhead is 19.712 bytes - 16 bytes = 3.712 bytes. The video rounds this to approximately 3 bytes per entry.

Comparing this to Redis’s 37 bytes overhead, DragonflyDB’s B+ Tree offers a massive reduction in memory footprint for the data structure itself.

Performance Benchmarks

DragonflyDB conducted benchmarks comparing its B+ Tree based Sorted Set implementation against Redis’s Skip List. The results highlight significant gains in both throughput and memory consumption.

The benchmarks involved firing millions of ZADD commands, with each command containing either 10-128 elements (small sets) or 129-200 elements (large sets).

Throughput (QPS) Comparison

Implementation	Small Sets (10-128 elements)	Large Sets (129-200 elements)
Redis (Single-threaded)	3.5K QPS	3.5K QPS
DragonflyDB (Single-threaded)	12K QPS	12K QPS
DragonflyDB (8-threaded)	83K QPS	83K QPS

Key Observations:

• DragonflyDB’s single-threaded performance is approximately 4 times better than Redis’s single-threaded performance.
• With 8 threads, DragonflyDB achieves an astounding 83K QPS, demonstrating its highly optimized and parallelizable architecture. This represents a nearly 25x improvement over Redis.

Memory Consumption Comparison

Memory consumption was also significantly lower for DragonflyDB, especially for larger Sorted Sets.

• Small Sets (10-128 elements): For small sets, where Redis uses listpack instead of Skip Lists, the memory difference between Redis and DragonflyDB was not as pronounced. listpack is already memory-efficient.
• Large Sets (129-200 elements): As the number of elements increased, the memory efficiency of DragonflyDB’s B+ Tree became evident. DragonflyDB consistently consumed less memory than Redis for the same workload, even with 8 threads. This directly correlates with the calculated overhead difference (3 bytes vs. 37 bytes).

Conclusion

DragonflyDB’s strategic choice to implement Sorted Sets using B+ Trees instead of Skip Lists yields substantial benefits. By meticulously optimizing the B+ Tree node structure to a fixed 256-byte array, DragonflyDB dramatically reduces the per-entry memory overhead from 37 bytes (in Redis’s Skip List) to approximately 3 bytes. This memory efficiency, combined with the inherent advantages of B+ Trees for range queries and the ability to leverage modern hardware parallelism, translates into significantly higher throughput and lower memory consumption, making DragonflyDB a compelling alternative for high-performance in-memory data storage.