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

41–50 of 205 posts

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

#41

Post by vkaku »

That's just a wrong assumption. In case anyone wants a '=' or 'in' query, you are better off keeping a hash index as opposed to an ordered index. Hash based partitioning is available on many commercially used DBs as well.

I would also like to point out that radix based storing is not a bad idea at all, and these data structures are never completely exclusive of each other :-)

I tend to disagree with the author because we can get into the details, but the article is a good read for someone who wants to understand how DBs/B-trees and scans work.

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

#42

Post by mercutio2 »

School-Cotton wrote: post #28
darawk wrote: post #16

Earlier quoted context omitted.

Also of note, hash tables (unless they are using perfect hashing) are not O(1). Big O notation refers to the worst case time, and the worst case time for a hash table is when the hash key is non-unique and the desired element needs to be looked up in a table. The relation between N and the complexity of this operation is somewhat implementation / data distribution dependent, but in the true worst case it is O(N) (all…

> Big O notation refers to the worst case time Not true. Big O notation can refer to worst case time, average case time, best case time, or any other possible mathematical function from integers or real numbers to real numbers. Big-O notation is in fact independent of computer science. It’s sometimes taught in calculus courses and used to describe arbitrary functions that have nothing to do with algorithm running tim…

Big-O in Bachmann–Landau notation specifically means the upper bound.

There are lots of other interesting measures of asymptotic behavior, and it's true that frequently in the vernacular Big-O is bandied as if it can mean many different things.

But I've never heard anyone in the computer science domain (which is surely what we're talking about when we're talking about hash tables?) argue that Big-O, when used precisely, is anything but upper bound.

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

#43

Post by halayli »

I believe it's more due to the fact that sorting, and less/greater than operators come up way more often in databases and using an ordered index makes a much better use case.

And the other reason is MVCC. It's easy to maintain multiple snapshots of a b-tree index and swap a root's ptr to point to a new sub-tree.

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

#44

Post by School-Cotton »

mercutio2 wrote: post #42
School-Cotton wrote: post #28

Earlier quoted context omitted.

> Big O notation refers to the worst case time Not true. Big O notation can refer to worst case time, average case time, best case time, or any other possible mathematical function from integers or real numbers to real numbers. Big-O notation is in fact independent of computer science. It’s sometimes taught in calculus courses and used to describe arbitrary functions that have nothing to do with algorithm running tim…

Big-O in Bachmann–Landau notation specifically means the upper bound. There are lots of other interesting measures of asymptotic behavior, and it's true that frequently in the vernacular Big-O is bandied as if it can mean many different things. But I've never heard anyone in the computer science domain (which is surely what we're talking about when we're talking about hash tables?) argue that Big-O, when used precise…

Yes. The upper bound of some function. That function is not necessarily the worst-case runtime.

Best-case, average-case, and worst-case can all have upper bounds.

If the best case runtime as a function of data size is n/2, average case is n^2 + 5x, and worst case is e^n + 5n^2, these functions are asymptotically upper bounded by n, 2n^2, and 2e^n respectively, so they are big-O (incidentally they are also big-Omega and big-Theta) of n, n^2, and e^n respectively.

Big-O means the same thing in CS as it does in mathematics; this is not an issue of different domains using terms in different ways.

See for example: https://stackoverflow.com/questions/42144251/why-is-big-oh-o... , https://stackoverflow.com/questions/3905355/meaning-of-avera...

A famous example is Quicksort which is O(n*log(n)) average case, but not worst case where the tightest big-O bound is O(n^2). Any reputable reference you look up will agree with this. From Wikipedia, for example: “Mathematical analysis of quicksort shows that, on average, the algorithm takes O(n log n) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though this behavior is rare.”

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

#45

Post by romwell »

Sometimes databases use hash tables for indexing.

This is a natural match for a key-value store.

In particular, the following KV stores offer hash table-based indexing:

-Berkeley DB [1]

-Tokyo Cabinet (and its successor, Kyoto Cabinet) [2]

-Bitcask (used in Riak) [3]

In many benchmarks, the hash-based systems perform better than tree-based ones.

The real advantage of trees, as Berkeley DB manual says:

> Btrees are better for range-based searches, as when the application needs to find all records with keys between some starting and ending value. Btrees also do a better job of exploiting locality of reference. If the application is likely to touch keys near each other at the same time, the Btrees work well.

And there is the actual answer to the question in the title. And that is the actual answer to the question (that, and optimiz

[1]https://docs.oracle.com/cd/E17275_01/html/programmer_referen...

[2]https://fallabs.com/tokyocabinet/perldoc/

[3]http://highscalability.com/blog/2011/1/10/riaks-bitcask-a-lo...

-----------------------

TL;DR: Why? Because you can do range queries and traverse sequential elements faster.

Don't need that? Use hash.

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

#46

Post by kadoban »

mercutio2 wrote: post #42
School-Cotton wrote: post #28

Earlier quoted context omitted.

> Big O notation refers to the worst case time Not true. Big O notation can refer to worst case time, average case time, best case time, or any other possible mathematical function from integers or real numbers to real numbers. Big-O notation is in fact independent of computer science. It’s sometimes taught in calculus courses and used to describe arbitrary functions that have nothing to do with algorithm running tim…

Big-O in Bachmann–Landau notation specifically means the upper bound. There are lots of other interesting measures of asymptotic behavior, and it's true that frequently in the vernacular Big-O is bandied as if it can mean many different things. But I've never heard anyone in the computer science domain (which is surely what we're talking about when we're talking about hash tables?) argue that Big-O, when used precise…

It is an upper bound on the growth. But _what_ you're upper bounding is not specified.

Big-O notation works on mathematical functions. In the usual case, the function you're upper bounding is the worst-case run time of a procedure for a given input size. But that's _far_ from the only case.

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

#47

Post by joe_the_user »

cwalv wrote: post #34
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…

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…

"Occasionally, when the table is growing, your normally fast O(1) insert involves a slow O(n) scan to move to a bigger table."

This my impression and it seems like it implies that the "hash table has O(1) access" is bullshit taken as a general formulation. The situation is essentially, hash tables can have "O(1) access" time at a certain size and if tuned for that size. BUT that seems an abuse of big-O notation, which is meant (originally, in math) to mean "as you go to infinity" and you can't really have a data structure that mains O(1) as it's size increases to infinity.

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

#48

Post by jdsully »

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.

If huge pages are used then it's very likely the page is cached in the MMU.

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

#49

Post by pwildani »

joe_the_user wrote: post #47
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…

"Occasionally, when the table is growing, your normally fast O(1) insert involves a slow O(n) scan to move to a bigger table." This my impression and it seems like it implies that the "hash table has O(1) access" is bullshit taken as a general formulation. The situation is essentially, hash tables can have "O(1) access" time at a certain size and if tuned for that size. BUT that seems an abuse of big-O notation, whic…

The actual analysis of inserts are that they take "amortized O(1) with a single operation worst case of O(N)"

So N operations take N measurement units as N goes to infinity, but any individual operation may be slower or faster.

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

#50

Post by [deleted] »

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.

[deleted]
Post reply on HN