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
Custom VMs From 1 to 96 vCPUs With 99.95% Uptime Icon
Custom VMs From 1 to 96 vCPUs With 99.95% Uptime

General-purpose, compute-optimized, or GPU/TPU-accelerated. Built to your exact specs.

Live migration and automatic failover keep workloads online through maintenance. One free e2-micro VM every month.
Start Free
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