The BList is similar to a B+Tree. It was meant to act like an array for small lists, but to make operations like append, concatenation, and slicing faster. It was a pretty cool combination of arrays (for memory compactness and good cache performance and small constant factors) with trees, for the asymptotic improvements they can bring.
Sadly, it didn't take off, as it would have broken backward compatibility with extension modules.
Comments
At one point, Python tried to move to something similar for their standard list data structure:
http://www.python.org/dev/peps/pep-3128/
The BList is similar to a B+Tree. It was meant to act like an array for small lists, but to make operations like append, concatenation, and slicing faster. It was a pretty cool combination of arrays (for memory compactness and good cache performance and small constant factors) with trees, for the asymptotic improvements they can bring.
Sadly, it didn't take off, as it would have broken backward compatibility with extension modules.
Some lisp and scheme implementations have used it as well, partly spurred by this 1994 paper: http://portal.acm.org/citation.cfm?id=182453
(I don't know offhand if any widely used ones currently do, though.)