The Design of Compact Elastic Binary Trees (Cebtree)
a year ago
- #data-structures
- #memory-management
- #optimization
- The article discusses the development and evolution of compact elastic binary trees (cebtree), a more space-efficient alternative to ebtrees.
- Initial work on self-organizing trees in 2007 led to the idea of arranging data without uplinks or depth relations, focusing on insertion and deletion efficiency.
- Optimizations using XOR operations between branches were explored to reduce storage needs and improve lookup efficiency.
- A limited implementation in 2014 for a 'water drop alloc' memory allocator demonstrated the feasibility of the compact tree concept with only two pointers per node.
- Challenges with performance and scalability led to pauses in development, but renewed efforts during lockdown in 2020 and later in 2023 resulted in functional versions (v0.1 and v0.2).
- The article highlights the successful integration of cebtree into haproxy for variable indexing, showing performance improvements.
- Future work includes documentation completion, exploring atomic operations, and potential merging with ebtree for enhanced functionality.
- Performance comparisons show cebtree is generally slower than ebtree due to additional memory reads but can be more efficient for small keys due to smaller node sizes.