[adrianN]

log(billions) is not very large, constant factors matter in practice. You can also do things with trees that are very difficult with hashes (e.g. ordered traversal). This is why databases still ship with tree indices.