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
PRTG Catches Network Issues Before They Cause Downtime Icon
PRTG Catches Network Issues Before They Cause Downtime

Threshold-based alerts flag problems early, so your team can act before users notice, not after.

Reactive troubleshooting usually means hearing about a problem from frustrated users, not your monitoring tool. PRTG sets threshold-based alerts across devices, servers and applications, notifying your team by email, SMS or push the moment a metric crosses a set limit. That means catching a failing disk or overloaded server before it becomes an outage and getting time back from firefighting. Start a free trial and set your first alerts today.
Download 30-Day Trial
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