5 ms·

>B-trees are the optimal implementation of dynamic arrays Then why don't the popular scripting languages use B-trees for their sequence containers? Both Perl

by crucini 12y ago

>B-trees are the optimal implementation of dynamic arrays Then why don't the popular scripting languages use B-trees for their sequence containers? Both Perl and Python use arrays for this. Both pay the price of O(n) inserts mid-container.

TJSomething 12y ago
I would be unsurprised if it was for legacy reasons. Both of those programming languages were written over twenty years ago. Furthermore, arrays play nicely with C extensions.
lrem 12y ago
Hmmm, let me shoot a quick guess: because B-trees are not an implementation of dynamic arrays?
TrainedMonkey 12y ago
I think there are several reasons: 1. Name array strongly implies that it has an underlying continuous memory location associated with it. All of modern scripting languages have some form of dictionary, map, set, or hashtable which is implemented using insert/update friendly approach. 1a. Typical workload for array is to iterate over it doing something with each element, B-Tree is strictly worse in iterating over all elements compared to static array. 2. Most instantiated dynamic arrays rarely perform deletes. Most common operation that could change size of array is push_back, and amortized cost for inserts is probably way less than chasing pointers in B-Tree. 3. B-Trees were created and optimized for HDD performance. With current SSD and memory trends, there are simply better data structures to use. 4. Pointer chasing got a lot more expensive relative to continuous memory scanning. This is mostly due to majority of memory performance increases coming from increased throughput as opposed to lower latency. This does not mean B-Trees are bad, in fact they are still heavily utilized in databases because they scale extraordinarily well with data size. They are commonly used for indexes because membership testing (single value lookup) and range lookups are O(1), and updates/deletes are generally very fast as well.
- crucini 12y ago
  I think this is a really good answer. However I slightly differ on #1. Python calls the default sequence container a list. If you took that literally, it implies O(1) inserts.
e12e 12y ago
Interesting question. For some discussion of (among other ADTs) "actual" trees in python, see: http://kmike.ru/python-data-structures/ http://kmike.ru/python-data-structures/ And: http://pythonhosted.org/BTrees/ http://pythonhosted.org/BTrees/
comex 12y ago
Cocoa switches away from straight arrays for large "array" objects: http://ridiculousfish.com/blog/posts/array.html http://ridiculousfish.com/blog/posts/array.html
kragen 12y ago
B-trees are “optimal” in the sense that they’re O(log N) for all the usual operations (insertion/deletion, appenditem, getitem, setitem, and even concatenation with some work) but simple exponentially-growing arrays are O(1) for getitem, setitem, and appenditem, which is asymptotically faster. Also, their constant factors are better, and their memory footprint is smaller. hyc_symas’s comment seems a little confused because they are talking about doing binary search within B-tree pages. But if you’re using B-trees to implement dynamic non-sparse arrays, which seems to be the topic, you don’t need any binary searches. You can just subtract the beginning-of-page index from the index you’re indexing to in order to get the offset within the page. That kind of comment, managing to be simultaneously ignorant and arrogantly dismissive, is why I don’t comment much on HN these days.
- hyc_symas 12y ago
  Sorry, but the only ignorance here is your own. You assumed that "storing into an array" means that the array index is the only thing relevant for locating a record. But the fact that you're talking about inserts/deletes means that the array index of a particular element is mutable and therefore insufficient for uniquely locating a record. Which means you must perform some type of search to retrieve a particular item. Your O(1) getitem is nonsense. Yes, you can say "give me the 5th element of this array" but the discussion was about maps/dictionaries, where you're more often going to say "give me item foo that was inserted before". When folks like you post while obviously not paying attention, yes, you elicit a dismissive response.

by crucini 12y ago

TJSomething 12y ago

I would be unsurprised if it was for legacy reasons. Both of those programming languages were written over twenty years ago. Furthermore, arrays play nicely with C extensions.

lrem 12y ago

Hmmm, let me shoot a quick guess: because B-trees are not an implementation of dynamic arrays?

TrainedMonkey 12y ago

I think there are several reasons: 1. Name array strongly implies that it has an underlying continuous memory location associated with it. All of modern scripting languages have some form of dictionary, map, set, or hashtable which is implemented using insert/update friendly approach. 1a. Typical workload for array is to iterate over it doing something with each element, B-Tree is strictly worse in iterating over all elements compared to static array. 2. Most instantiated dynamic arrays rarely perform deletes. Most common operation that could change size of array is push_back, and amortized cost for inserts is probably way less than chasing pointers in B-Tree. 3. B-Trees were created and optimized for HDD performance. With current SSD and memory trends, there are simply better data structures to use. 4. Pointer chasing got a lot more expensive relative to continuous memory scanning. This is mostly due to majority of memory performance increases coming from increased throughput as opposed to lower latency. This does not mean B-Trees are bad, in fact they are still heavily utilized in databases because they scale extraordinarily well with data size. They are commonly used for indexes because membership testing (single value lookup) and range lookups are O(1), and updates/deletes are generally very fast as well.

crucini 12y ago
I think this is a really good answer. However I slightly differ on #1. Python calls the default sequence container a list. If you took that literally, it implies O(1) inserts.

e12e 12y ago

Interesting question. For some discussion of (among other ADTs) "actual" trees in python, see: http://kmike.ru/python-data-structures/ http://kmike.ru/python-data-structures/ And: http://pythonhosted.org/BTrees/ http://pythonhosted.org/BTrees/

comex 12y ago

Cocoa switches away from straight arrays for large "array" objects: http://ridiculousfish.com/blog/posts/array.html http://ridiculousfish.com/blog/posts/array.html

kragen 12y ago

B-trees are “optimal” in the sense that they’re O(log N) for all the usual operations (insertion/deletion, appenditem, getitem, setitem, and even concatenation with some work) but simple exponentially-growing arrays are O(1) for getitem, setitem, and appenditem, which is asymptotically faster. Also, their constant factors are better, and their memory footprint is smaller. hyc_symas’s comment seems a little confused because they are talking about doing binary search within B-tree pages. But if you’re using B-trees to implement dynamic non-sparse arrays, which seems to be the topic, you don’t need any binary searches. You can just subtract the beginning-of-page index from the index you’re indexing to in order to get the offset within the page. That kind of comment, managing to be simultaneously ignorant and arrogantly dismissive, is why I don’t comment much on HN these days.

hyc_symas 12y ago
Sorry, but the only ignorance here is your own. You assumed that "storing into an array" means that the array index is the only thing relevant for locating a record. But the fact that you're talking about inserts/deletes means that the array index of a particular element is mutable and therefore insufficient for uniquely locating a record. Which means you must perform some type of search to retrieve a particular item. Your O(1) getitem is nonsense. Yes, you can say "give me the 5th element of this array" but the discussion was about maps/dictionaries, where you're more often going to say "give me item foo that was inserted before". When folks like you post while obviously not paying attention, yes, you elicit a dismissive response.