B-trees with augmented information are very fast, and I know of no generic augmented B-tree. So I've contributed to a program that shipped a custom augmented b-tree. I assume the same goes for other types of augmented data structures. Is that so rare ? Or do most people simply not know how/why to augment data structures ?