flâneur

Why databases use ordered indexes but programming uses hash tables (evanjones.ca)

evanjones.ca · 1,612 words · saved by 1 readers

I think it is safe to state that hash tables (e.g. maps in Go, dicts in Python, HashMap in Java, etc.) are far more common than ordered data structures such as trees for in-memory data structures. One data point is that in a talk about C++ hash table optimization at Google (available in Abseil), the speaker noted that 1% of CPU and 4% of RAM globally at Google is used by hash tables. However, in databases, the default is almost always an ordered index, typically a B-Tree. Why is the "default" choice different between programs and databases, when at the end of the day they both do the same thing: accessing data for our code? More than a year ago I asked about this out loud on Twitter, and got many interesting answers. This is my very delayed attempt to distill what I've learned. [Note 2019-12-15: Added a paragraph about locality of reference.] The traditional answer is that hash tables are designed to be efficient when storing data in memory, while B-Trees are designed for slower storag

Why databases use ordered indexes but programming uses hash tables (evanjones.ca) Why databases use ordered indexes but programming uses hash tables about | archive [ 2019-December-08 16:34 ] I think it is safe to state that hash tables (e.g. maps in Go, dicts in Python, HashMap in Java, etc.) are far more common than ordered data structures such as trees for in-memory data structures. One data point is that in a talk about C++ hash table optimization at Google ( available in Abseil ), the speaker noted that 1% of CPU and 4% of RAM globally at Google is used by hash tables. However, in databas

related reading