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
MongoDB Atlas runs apps anywhere Icon
MongoDB Atlas runs apps anywhere

Deploy in 115+ regions with the modern database for every enterprise.

MongoDB Atlas gives you the freedom to build and run modern applications anywhere—across AWS, Azure, and Google Cloud. With global availability in over 115 regions, Atlas lets you deploy close to your users, meet compliance needs, and scale with confidence across any geography.
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

Information Technology, Science/Research, Developers

Programming Language

C

Related Categories

C Algorithms, C Libraries

Registered

2013-06-21