As an alternative to a B+Tree, using Bitmap Indexes (http://en.wikipedia.org/wiki/Bitmap_index) could allow a very speedy retrieval of simple queries like the equivalent of "SELECT * FROM FOO WHERE GENDER = "MALE" AND "STUDENT" = TRUE.

Bitmap indexes used to be thought of a "low cardinality" thing, but in "An Adequate Design for Large Data Warehouse Systems: Bitmap index versus B-tree index" by Zaker et al, the authors go even as far as saying that for certain situations, the cardinality of the values does not even matter. Their conclusive statement is as follows:

Thus, we conclude that Bitmap index is the conclusive choice for a DW designing no matter for columns with high or low cardinality.

A highly optimized C++ library called Fastbit (https://sdm.lbl.gov/fastbit/) already exists.

Especially when using large amounts of data that have a low cardinality (e.g. a 'gender' field), the compressed bitmap indexes could keep the RAM usage low and outperform B+Trees.