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
Paessler: Easy to Use With Enterprise Power. Free Trial
You shouldn't have to choose between a monitoring tool that's easy to use and one that's powerful enough for a complex environment. PRTG's low-code interface lets any admin build dashboards, set alerts and monitor devices without scripting, while custom sensors and full API access are there when your team needs deeper control. One platform, no compromise. Download a free 30-day trial now.
Rate This Project
Login To Rate This Project
User Reviews
Be the first to post a review of Capsule Tree!
