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

[barnesc at engr.orst.edu]

Nifty, Tim Peters responded to my e-mail.  I must've said something
interesting.  Cool, a PyCelebrity!

>[barnesc at engr.orst.edu]
>> ...
>> I've gotten bored and went back to one of my other projects:
>> reimplementing the Python builtin classes list(), set(), dict(),
>> and frozenset() with balanced trees (specifically, counted B-trees
>> stored in memory).
>>
>> In short, this allows list lookup, insertion, deletion in O(log(N))
>> time.  It allows the set and dictionary types to be maintained in
>> order, and insert/lookup/remove operations here take O(log(N)) time
>> as well.  Getting the k least or k greatest elements takes
>> O(log(N)+k) time.
>
>Note that BTrees for Python have been part of ZODB for many years:
>
>    Section 5.3, _BTrees Package_
>    http://www.zope.org/Wikis/ZODB/FrontPage/guide/node6.html
>
>If you install ZODB, you can use its BTrees as in-memory data
>structures without using any of the rest of ZODB.  If you want to
>persist them, great, that's what ZODB is for.
>
>Note that ZODB's are really B+ trees, so iterating over the smallest k
>takes O(k) time.  As an extension to Python's mapping protocol, the
>keys/values/items/iterkeys/itervalues/iteritems methods also accept
>optional lower and upper bounds on the keys to return.
>
>A gotcha:  For scalability in multiprocess database apps, ZODB's
>BTrees do not store their size.  As a result, len(a_ZODB_BTree) takes
>time linear in the number of elements.

Thanks for the link!

>> ...
>> So my question is: are there any other *practical* applications of a
>> B-tree based list/set/dict ?
>
>Yes.
>
>> In other words, is this module totally worth coding,
>
>That's a different question entirely ;-)
>
>> or is it just academic wankery and theoretical flim flam ? :)
>
>It's probably not a way to get rich quick.
>

Well, the Tim Peters PyCelebrity experience was fun, but not quite
as exhilarating as advertised.  I'm not sure what to say.  Did I get
my money's worth?  There were no <wink>s, even a little sarcasm.  I
guess, overall, yeah it was cool, it was worthwhile, it was fun, man,
it was a life-changing moment!

Thanks for tuning in to PyCelebrity weekly.  We're always glad to
be part of your inexplicable existence in The Hostile And Indifferent
Universe (Incorporated).  Contributions come from hackers like you!

 Reporting live from Python-list, this is...Connelly Barnes.

 Next up: Startling photographs show that Guido van Rossum was
          KIDNAPPED BY ALIENS in 1990!  Rumor has it that his
          superhuman language design skills are really due to
          neuroimplanted nanotube processors!