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

Project Activity

See All Activity >

Categories

Algorithms, Libraries

License

GNU General Public License version 2.0 (GPLv2)

Follow Capsule Tree

Capsule Tree Web Site

Other Useful Business Software
Already Paying for an RMM? Get 50% Off Splashtop AEM Icon
Already Paying for an RMM? Get 50% Off Splashtop AEM

Switch to Splashtop AEM and save up to 50% in your first year

Automated OS and third-party patching for Windows and macOS, CVE prioritization with AI patch summaries, and built-in remote control that also supports Linux. Qualifying organizations switching from another RMM get up to 50% off year one.
Get Started
Rate This Project
Login To Rate This Project

User Reviews

Be the first to post a review of Capsule Tree!

Additional Project Details

Intended Audience

Developers, Information Technology, Science/Research

Programming Language

C

Related Categories

C Algorithms, C Libraries

Registered

2013-06-21