• FolderShare used this in the backend to hold trees with 1-50,000 items. Performance was great, and we were really satisfied with it.

• Each non-inline item stored in the tree requires 4 pointers and an enum, which may take up to 40 bytes. With heap overhead, this results in almost 50 bytes of overhead per tree item. For some uses, this can be reduced by inlining your data in the tree item. But, be sure to take into account this overhead when considering how many items a single server can hold in memory.

* Kazlib, the most solid, flexible, no-nonsense, gets-out-of-your-way data structures library you'll ever use. Has a doubly-linked list, red-black tree, and hash table. Lets you handle all your own allocation if you want to, and minimizes its memory footprint.

How a redblack tree works