Builtin classes list, set, dict reimplemented via B-trees

[Bryan Olson]

barnesc at engr.orst.edu wrote:
 > Here overhead is compared to a C array of > 1 million PyObject *s.
 >
 > Thus, on average, a > 1 million element B-tree uses 25% less memory
 > than any other balanced data structure which I am aware of, and 50%
 > more memory than a raw C array.

That's overhead of indexing; it doesn't consider the space
already used to store the keys and values. The B-tree can get by
with modestly fewer pointers, because it has fewer internal
nodes that need to be referenced by other internal pointers.
That assumes that the B-tree nodes are kept as linear arrays,
which means that either inserting into them will time
proportional to the fan-out, or searching them will.

[...]
 > I have no idea how B-trees compare to skip lists (the likely
 > contender) in terms of speed.

I'd expect Red-Black trees to be at least as good a contender.

 > Are there any *practical* applications for in-memory balanced data
 > structures (e.g. skip list, AVL tree, RB tree, B tree) ?

Yes, absolutely. Efficient ordered sub-ranges; efficient rank
queries; sustainable performance with adversarial inputs.


-- 
--Bryan