Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why databases use ordered indexes but programming uses hash tables

evanjones.ca

Post reply on HN
Print view View original

151–160 of 205 posts

Re: Why databases use ordered indexes but programming uses hash tables

#151

Post by taejo »

Thorrez wrote: post #133
LessDmesg wrote: post #105

Earlier quoted context omitted.

malloc() isn't O(1), but allocations in a normal GC are O(1).

Is there some reason that malloc() would be slower asymptotically than a GC? Why couldn't whatever technique is used for the fast GC be used for malloc() as well?

GCs are typically allowed to (and often do) move objects, while malloc/free do not. This means that malloc/free must maintain data structures tracking allocated vs. free space, while compacting GCs keep all the free space in a single contiguous address space, so allocating an object just increments the "start of free memory" pointer.

Re: Why databases use ordered indexes but programming uses hash tables

#152

Post by rklaehn »

lichtenberger wrote: post #145
rklaehn wrote: post #117

Databases use hashes all the time, also ordered indexes are very frequently used in programming (e.g. C++ stl). I think ordered indexes are a good default for use in programming languages. They are deterministic and do not have strange corner cases that can be exploited. E.g. the order when iterating over elements in a hashtable is pretty much random, whereas the order of elements in an ordered tree based data struct…

You can also implement a hash map as a tree ;-)

Been there, done that... :-)

Re: Why databases use ordered indexes but programming uses hash tables

#153

Post by cesarb »

cperciva wrote: post #37
geophile wrote: post #20

I think this article misses two points more important than anything else mentioned. 1) B-trees are dynamic while hash tables are not. A B-tree grows gracefully across orders of magnitude, and shrinks just as easily. Most hash tables do not have this property. Extensible hashing, and linear hashing do grow and shrink gracefully, but I'm not sure how widely used they are. 2) In a database system, the concern was tradit…

On modern hardware a key lookup in a hash table isn't necessarily a single page read! Sure, it's a single virtual memory access, but if that page isn't in your TLB you need to read the page table... and if the page containing that part of the page table isn't in the TLB you need to read that page... On modern hardware, every memory access looks very much like a B-tree lookup.

> and if the page containing that part of the page table isn't in the TLB you need to read that page...

I thought page tables used physical addresses, which are accessed directly without any TLB lookup (except when nested paging during virtualization, which adds another level of indirection). Of course, the processor still needs to read each level into the data cache(s) while doing a page table walk.

Re: Why databases use ordered indexes but programming uses hash tables

#154

Post by AstralStorm »

geophile wrote: post #68
cwalv wrote: post #34

Earlier quoted context omitted.

Didn't the article address 1) with this?: > Another difference is that hash tables only provide average constant time accesses. Bad behaviour can be caused by hash collisions, either unintentional or malicious, but a bigger issue is rehashing. Occasionally, when the table is growing, your normally fast O(1) insert involves a slow O(n) scan to move to a bigger table. The impact of this can be reduced by using multi-le…

No. This discussion is about algorithmic complexity, typically counting comparisons. And of course, it ignores constants. If we're counting page accesses, we care very much about the constants. And furthermore, a "multi-level hash table" is a tree, except an unordered one. What a useless beast!

Yes, mostly. There are better structures with these characteristics like a skiplist, multihashed table (typically double hashed) or extensible hashing.

Re: Why databases use ordered indexes but programming uses hash tables

#155

Post by branko_d »

geophile wrote: post #20

I think this article misses two points more important than anything else mentioned. 1) B-trees are dynamic while hash tables are not. A B-tree grows gracefully across orders of magnitude, and shrinks just as easily. Most hash tables do not have this property. Extensible hashing, and linear hashing do grow and shrink gracefully, but I'm not sure how widely used they are. 2) In a database system, the concern was tradit…

Yup, aligning the B-Tree nodes to database pages (which are themselves aligned to physical disk blocks) is the key.

No pun intended ;)

Re: Why databases use ordered indexes but programming uses hash tables

#156

Post by dreamcompiler »

I use two structures for persistent data: Extendible hashing for unordered data and skip lists for ordered data. Extendible hashing is great for looking up an object given its UID. Skip lists are easier than B-trees (to me) for everything else. I also use skip lists occasionally for in-memory data because they're just so darn handy. I wish both were better known.

Re: Why databases use ordered indexes but programming uses hash tables

#157

Post by jtc331 »

travisjungroth wrote: post #26
whack wrote: post #15

Earlier quoted context omitted.

> Essentially I don’t think it’s really enough to consider the asymptotic complexity of algorithms to compare practical runtimes. You need to know what the smaller-order / constant terms are. Nitpick: even if you know the constant terms, that would only tell you the number of operations required to execute the code. That's not enough to compare runtimes, because runtimes are also impacted by other factors like branch…

This is why benchmarking can be useful. I’m not sure why in a field where the materials cost of testing an idea is zero it’s done so much less frequently than theorizing.

Maybe because that commits you to a specific implementation with all of its particular choices instead of being able to compare the class of problems and solutions.

Edit: Typo.

Re: Why databases use ordered indexes but programming uses hash tables

#158

Post by narnianal »

I would very simply summarize it like this: If you know which data you look for and say "give me this piece" then you want to use a hash table. If you don't know what you are looking for and need to filter/search, then you use a b-tree. So actually you want to use both structures regularly.

Not sure how that general principle really applies or if it's just a quirck my brain came up with, though. If you look at distributed hash tables for instance, they are hash tables on a bus network in some sense, but they are used for search/filter tasks over multiple nodes.

Re: Why databases use ordered indexes but programming uses hash tables

#159

Post by estebarb »

I think that people just take too seriously the part of "hash tables are O(1) and trees are O(log(n))". But you have to consider complexity of hash generation (in real life sometimes it's worse than tree traversal), rebalancing, order lost and programmer issues (some just ignore at all that hash collisions do happen). At least in my case, I have found that skipkists have similar performance than hash tables (ops/seq for real life loads, not infinite items), and use less memory (at least the Open vSwitch implementation).

Re: Why databases use ordered indexes but programming uses hash tables

#160

Post by cesarb »

taejo wrote: post #151
Thorrez wrote: post #133

Earlier quoted context omitted.

Is there some reason that malloc() would be slower asymptotically than a GC? Why couldn't whatever technique is used for the fast GC be used for malloc() as well?

GCs are typically allowed to (and often do) move objects, while malloc/free do not. This means that malloc/free must maintain data structures tracking allocated vs. free space, while compacting GCs keep all the free space in a single contiguous address space, so allocating an object just increments the "start of free memory" pointer.

Of course, that just moves the cost from the allocation side to the GC side. This means that the GC must maintain data structures tracking the type of each object (to know which fields are references), the root references, and several others (like card tables) for an efficient implementation. For malloc/free, releasing an object can just add it to a free list (a pair of pointer writes), while a compacting GC has to update all references pointing to the live objects it moves.
Post reply on HN