Why databases use ordered indexes but programming uses hash tables
1–10 of 205 posts
Re: Why databases use ordered indexes but programming uses hash tables
#2I think part of it is inertia. There was a time when C++ only had a tree based map, but eventually it got a hash map too.
And part of it is that a database needs a sorted index. Because a lot of common queries would be awful without one. And when you have a sorted index already, a hash index becomes a nice-to-have.
Re: Why databases use ordered indexes but programming uses hash tables
#3Thanks for posting this article. The link to the b-tree monography itself is gold. Kudos!
Re: Why databases use ordered indexes but programming uses hash tables
#4Nit-pick / pet-peeve regarding Big O notation!
> Hash tables provide constant time O(1) access for single values, while trees provide logarithmic time O(log n) access. For single value lookups, this means hash tables are faster,
> for small n, the hash table is better, but for large n, the cost of that rare scan dominates, and the tree is better
The Big O notation describes how the number of operations scales as the size of the input tends to infinity: the asymptotic complexity. This means that an O(1) algorithm can include some fixed number of operations, even enough to add _years_ onto the runtime, and still be classed as O(1).
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.
Re: Why databases use ordered indexes but programming uses hash tables
#5For one, a database may receive a query such as "WHERE x >=10 AND x <=100". I.e. having an ordered index is useful for accessing ranges, whereas a hash lookup is always just for a single entry. The question then becomes - why are lookups in RAM more likely to be single lookups rather than ranges (and stats on ranges)? Partly at least because DBs provide a query language that make range based queries easy to do, and just because that's where most business data sits (most of it necessarily needs to be in a persistent store).
Re: Why databases use ordered indexes but programming uses hash tables
#6Also, the log N constant is much smaller on disk than in memory, because the branching factor is really high.
Re: Why databases use ordered indexes but programming uses hash tables
#7I think part of it is inertia. There was a time when C++ only had a tree based map, but eventually it got a hash map too. And part of it is that a database needs a sorted index. Because a lot of common queries would be awful without one. And when you have a sorted index already, a hash index becomes a nice-to-have.
Adding to that, a database typically has to be ready for all kinds of queries. But when choosing a data structure in a program, one often knows a great deal about exactly what queries will show up.
Re: Why databases use ordered indexes but programming uses hash tables
#8See also:
Extendible hashing—a fast access method for dynamic files
Re: Why databases use ordered indexes but programming uses hash tables
#9* In most databases you can explicitly specify the kind of index, for example Postgres:
CREATE INDEX name ON table USING hash (column);
https://www.postgresql.org/docs/9.1/indexes-types.html
* In databases, ORDER BY is regularly used, making hash indexes as a default a bad choice
* See also https://en.wikipedia.org/wiki/B-tree#Advantages_of_B-tree_us...: The B-tree uses all of the ideas described above. In particular, a B-tree: keeps keys in sorted order for sequential traversing uses a hierarchical index to minimize the number of disk reads uses partially full blocks to speed insertions and deletions keeps the index balanced with a recursive algorithm In addition, a B-tree minimizes waste by making sure the interior nodes are at least half full. A B-tree can handle an arbitrary number of insertions and deletions.
Re: Why databases use ordered indexes but programming uses hash tables
#10[deleted]