Hacker News new | past | comments | ask | show | jobs | submit login

* 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.




Real implementations of B-Trees (i.e. B+Trees) don't preserve the traditional guarantee about nodes being half full. However, space utilization is still a big advantage.

You can't do efficient retail deletes with hash indexes in the presence of duplicates because it isn't possible to append a unique-ifier (e.g. table TID) to the key, for exactly the same reason as it isn't generally possible to support multi-column indexes. In the case of Postgres hash indexes, it doesn't matter as much because VACUUM doesn't currently do retail deletions in any case. Postgres B-Tree indexes should support retail deletion at some point in the future, but that hasn't happened yet.

Also, deleting whole B-Tree pages (removing them from the tree entirely) can be thought of (and implemented) as an operation that is symmetric to page splits. Page deletion is especially complicated at the best of times, because it's particularly hard to reason about race conditions (Postgres has many layers of indirection to get this to work). I can't imagine anything that would work as well, but with hash indexes.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: