In the Linux kernel, the internal Red-Black tree (rbtree) implementation uses this trick to save memory. Quoting LWN: "The anticipatory, deadline, and CFQ I/O

In the Linux kernel, the internal Red-Black tree (rbtree) implementation uses this trick to save memory. Quoting LWN: "The anticipatory, deadline, and CFQ I/O schedulers all employ rbtrees to track requests; the packet CD/DVD driver does the same. The high-resolution timer code uses an rbtree to organize outstanding timer requests. The ext3 filesystem tracks directory entries in a red-black tree. Virtual memory areas (VMAs) are tracked with red-black trees, as are epoll file descriptors, cryptographic keys, and network packets in the "hierarchical token bucket" scheduler." http://lwn.net/Articles/184495/ http://lwn.net/Articles/184495/