[EMAIL PROTECTED] 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 -- http://mail.python.org/mailman/listinfo/python-list