capsule tree

We have hosted the application capsule tree in order to run this application in our online workstations with Wine or directly.

Quick description about capsule tree:

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

Audience: Information Technology, Science/Research, Developers.

Programming Language: C.

.