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.
RubyTree is a simple to use general purpose tree data structure implementation in Ruby. It provides easy access methods for navigating the hierarchy, as well as for accessing the nodes. It also provides ability to marshal the entire tree structure. The library provides a generic tree as well as a binary tree implementation. It is available as a RubyGem or standard Tar/ZIP packages.
BS is a data structures library. It features fixed size, random access sequences. The sequences are constructed over B-trees. Complexity for most single item operations is about O(logN). The sequences are three to five times faster over random access BST-based sequences, while having better memory usage characteristics.