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.


  • 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 >


Algorithms, Libraries

Follow Capsule Tree

Capsule Tree Web Site

Other Useful Business Software

Any Platform Anywhere: The Best Workflow Software Any Platform Anywhere: The Best Workflow Software Icon
Any Platform Anywhere: The Best Workflow Software Icon

Empower employees to improve their productivity with nocode process automation tools.

Most people intuitively understand how workflows can streamline and speed up their business processes, integrate systems and route content to the right people. While every business has different needs, requirements and goals, workflow automation can help everyone. Whether you’re a company of 500 or 5,000, based in the cloud or on-premises, workflow automation can help maximize the efficiency of your business processes.

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