Download
A capsule tree is a general purpose, self-balancing tree data structure for large, ordered, data-sets. It is designed to provide the same characteristics as B-trees and B+trees, but built from the ground up for in-memory usage. In other words, there are no provisions for “slow” I/O cases.
The original motivation for this tree was a better backend for memory managers.
However, the end result was a new sub-category of trees. The implementation giving here is just one implementation of the new tree sub-category, there can be others.
In any case, read the PDF: “Capsule Trees - A Primer”, before delving into the code.
Features
- Designed to scale while reducing pointer chasing
- Designed for in-memory usage (unlike B-trees and B+ trees)
- In-node element placement (unlike B+ tree)
- Is its own min and max heap (while maintaining lookup in logarithmic time)
- Inherently by-order, bi-directional, traversable
License
GNU General Public License version 2.0 (GPLv2)Follow Capsule Tree
Other Useful Business Software
AI-generated apps that pass security review
Retool lets you generate dashboards, admin panels, and workflows directly on your data. Type something like “Build me a revenue dashboard on my Stripe data” and get a working app with security, permissions, and compliance built in from day one. Whether on our cloud or self-hosted, create the internal software your team needs without compromising enterprise standards or control.
Rate This Project
Login To Rate This Project
User Reviews
Be the first to post a review of Capsule Tree!
