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 traditionally to minimize page accesses. CPU is not negligible, and now there are main memory databases, as well as RAM sizes much larger than they were in the 70s and 80s. However, a lot of the main ideas in traditional OLTP databases were developed a long time ago, and the resulting architecture is still very much in use. So how many page reads to do a key lookup in a hash table? One. End of story. How many page reads to do a key lookup in a B-tree? Or to be more precise, a B+-tree, which has a much higher branching factor? Probably one. The root, and most likely the second level of pages stay cached, so it's really one page access to get a 3rd-level page. And, of course, as mentioned in the article, B-trees give you sequential access in key order, for when that's important.
On modern hardware, every memory access looks very much like a B-tree lookup.
Making a 48-bit B-tree would have a bit of a memory problem making TLB huge.
And then CPU cache is an array. Single virtual memory access is bound to be a single physical as well, with minor exceptions for NUMA nodes being crossed.
I thought page tables used physical addresses, which are accessed directly without any TLB lookup (except when nested paging during virtualization, which adds another level of indirection). Of course, the processor still needs to read each level into the data cache(s) while doing a page table walk.
When the virtual address you're looking to resolve is not present in that cache (i.e. when you have TLB miss), the CPU falls back to walking the page table hierarchy. At each level of the tree, the CPU reads an physical address of the next level of the tree and performs a memory fetch of that page table entry (in my previous comment I erroneously said a "page fetch", but it's actually only performing a cache-line sized fetch) and repeatedly so until it reaches the leaves of the tree which contain the Page Table Entry that contains the physical address of the (4k) physical page associated with the virtual page address you wanted to resolve.
Is that really likely on a production database server?
Indexes have lower computational complexity for certain tasks (in particular range queries & sort), but higher constants than typical hashing.
Thus indexes make more sense with two-tiered memory; to cache in RAM metadata about data kept in block storage.
How that could be put to good use with the L1 cache being much faster than RAM is anyone's guess.
 without guessing, we already know a small interpreter that fits in L1 can be blazing fast.
> 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-level hash tables, but it still causes some unpredictability. Trees, on the other hand, have worst case performance of O(log n).
And furthermore, a "multi-level hash table" is a tree, except an unordered one. What a useless beast!
Mostly but not entirely. There are cases where you need a tree but you don't care about order, e.g. when order depends on a state that is unknown at time of writing or when all you want to encode are relationships.
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.
At the level of abstraction that comexity analysis is usually done, you can. For example, a lookup in an array (a[X]) has O(1) worse-case complexity no matter how large the array is.
Of course, this relies on a few abstractions - that random memory access has uniform cost; and that basic numeric operations have uniform cost regardless of the size of the operands. Of course, in real computers, both of these assumptions are wrong (adding terabyte-size numbers is not as fast as adding byte-sized numbers, large amounts of memory can't usually be stored on random-access hardware etc.), but that does not necessarily impact the usefulness of complexity analysis.
For hash-tables in particular, the worse-case complexity for key lookup depends on some guarantees from the hash algorithm. If you had a magical hash that is unique for any key in your domain, than lookup would be O(1) for a hash table of n elements, as n approaches infinity. Since that is not a good abstraction, we need to model the table using hash functions that can create collisions, and the worse case becomes that O(n) elements collide and get put into the same bucket, giving worse-case complexity of O(n). Adding elements to the hash table is a different operation, same as for the array.
Formally it's amortized O(1) time and pessimistic O(n) time.
It's not abuse - many algorithms and data structures have different performance in average and worst case - for example quicksort is O(n log n) but in worst case it's O(n^2). People just ignore the worst case unless worst-case guarantees are especially important for their system.
So N operations take N measurement units as N goes to infinity, but any individual operation may be slower or faster.
If lucky transactions are more than fast enough but unlucky transactions time out because they perform a rebuild it's a defect that cannot be accepted because average performance is good.
Most databases need to take care of worst case performance with techniques that increase complexity and degrade best-case and aggregate performance (e.g. maintaining two hash tables, with lookup accessing both, insertions into the preferred one, and background threads that move records from the old table to the new table).
> Some hash table implementations, notably in real-time systems, cannot pay the price of enlarging the hash table all at once, because it may interrupt time-critical operations. If one cannot avoid dynamic resizing, a solution is to perform the resizing gradually.
But I'm not sure incremental resizing can get to actual O(1). Is the malloc() call for the new memory O(1)? And then after malloc() wouldn't the memory have to be initialized somehow (maybe just 0-initialized)?
Doing more work but elsewhere can (possibly) make your program faster. GC's often eat more CPU and RAM which hurts when you need more of either. But C/C++ can occasionally put malloc pressure on your critical path hurting you when you have plenty of resources where a GC might actually help you.
If it was any simpler it wouldn't be so damn interesting and fun.
To free, add the block to the appropriate free list. Assume blocks participate in a doubly-linked list of all blocks, used and free alike, in address order - adjacent free blocks can be coalesced at this point.
See section IV 4 E, "range queries" in "A comparison of adaptive radix trees and hash tables" (2015)
Even for the best hash table-based indexing B+Trees win. And combining this with the big cost of resizing (growing) or rehashing a table (rebalancing, i.e. Cuckoo) they are not useful.
Perhaps some adaptive hashing method could take care of this in the future.
No pun intended ;)
Is it really about memory access or disk loads?
Though btrees are friendly to cpu caches too, but really it's about minimising disk accesses.
I guess it depends what your definition is of ‘graceful’.
A typical hash table is not graceful in this way, because while each insert is O(1), you occasionally need to rehash everything into a bigger table, and that is O(n). As I noted above, linear and extensible hashing avoid this problem. An insert that forces a reorg just reorgs one bucket.
All hashtable requires rehashing up to certain fill rate, otherwise it will regress to linear look up. For the two most popular implementations, linked-list based or open addressing based, the common strategy for rehashing is to create another instance of hash table and copy the KV over. But on disk, this will be disastrous.
> 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.
An example of a galactic algorithm is the fastest known
way to multiply two numbers, which is based on a
1729-dimensional Fourier transform. This means it will
not reach its stated efficiency until the numbers have
at least 21729 digits
Not 21729 digits, but 2^1729 digits. Practically unusable in any real world case.
HN submission with related comments: https://news.ycombinator.com/item?id=17177798
Hash tables are bounded below by the speed of arithmetic. A trillion-bit number takes a while to multiply. You may have never touched a trillion-bit number, but it's called "asymptotic" for a reason.
You only get O(1) if you use a model of computation in which arithmetic is constant time. It's simple to work with, even though it's not realistic, and opens up scenarios where you can encode a really complex operation into adding/multiplying some huge numbers, and then claim the overall computation is still fast.
Some theorists use a model of computation in which, if your input size n, then multiplying a log-n bit number is O(1), but multiplying an n-bit number is O(n). I have no idea how this is well-defined.
So saying such a structure has O(1) asymptotic access time is not perfectly true in a mathematical sense, for unrealistic numbers. But it's certainly realistic.
I'd proposed a model in a sibling comment that seems to be the one most people use for analyzing algorithms.
The model of computation used in these analyses and interview questions I'd say is a random-access infinite register machine of infinite size (and constant arithmetic), which is more powerful than a TM (and siblings) in complexity analyses.
Of course, they are useless for analyzing complexity classes of computational problems, but you can use them to talk about the complexity of computer algorithms.
But it is, and that's precisely the reason why hash tables are not O(1) but rather O(log(n)). By the pigeon hole principle, it is impossible to store N items in a hash table using a key whose representation is less than log(N) bits without a collision. This means that there is a relationship between the the size of the key being hashed and the number of elements being inserted in the hash map, specifically the relationship is an element of O(log(n)).
I'm sorry, but as a reader it is quite amusing that various posters are claiming (all without citing any sources) hashtables are O(1), O(n) and O(log(n))
This makes it effective O(1) but worse case O(log n).
If you think about it, a hashtable isn't really that different from a b-tree with a very large value for "b".
No HashTable implementation worth it's salt is going to have a fixed size table. They are going to dynamically grow the size of the table (double it) once certain level of utilization is reached in the table (say 50%). In practice this means that chains at the same bucket will be of some small constant length assuming a good hash function.
Nitpick: even if you know the constant terms, that would only tell you the number of operations required to execute the code. That's not enough to compare runtimes, because runtimes are also impacted by other factors like branch prediction rate and cache hit rate. You need to consider those factors as well, in order to compare runtimes.
At some point, articles become completely unreadable when they try to address every possible nitpick. Some tangents are better left unexplored in a blog post.
If they were zero, the testing would already be done.
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 times.
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.
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.”
I tried to make this clear in my comment - (asymptotic) "upper bound" is a concept applicable to any function from N to R. So do you mean the upper bound of the worst case, the upper bound of the average case, the upper bound of the best case, the upper bound of the worst case memory usage, the upper bound of the median price of eggs in China on the nth day since 1970, or something else?
> They are not different functions. They are the same function.
Sure, if you expand the term "function" to include "random variable", which is legitimate to do in some fields of math... but we're talking about deterministic functions from the natural numbers (or real numbers) to the real numbers here. Which is what big-O notation is defined for.
Can you write down the deterministic function from N->R giving the "runtime" of some algorithm? (I mean the actual function, not big-O).
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.
The other notations (small o and omega) are about scaling (small o doesn't allow constant factors) and pinching (omega means there are two constant factors, one of which forms a lower bound, and the other an upper bound.
True, the word amortized (i.e. average) is left out here, which still makes people's usage imprecise. But there is a decent argument that amortized is more meaningful than worst-case. Because amortized gives expected throughput and latency, whereas worst-case says very little about throughput and only informs you on the 99th percentile of latency.
* In databases, ORDER BY is regularly used, making hash indexes as a default a bad choice
* See also
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.
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.
- It is much easier to write a transparently correct comparison method for a new object that I want to use as a key. With hash tables you need to worry that your hash function might not be properly distributed.
- With hash tables you have to worry that your language's under-the-hood resize/reallocate algorithm works well, or you need to make sure you choose the capacity and load factor numbers correctly. Even if things work as expected, you might end up paying a penalty because, for example, the array backing the hashtable was auto-resized to 128 million elements when you only need 70 million.
- Java TreeMap has lots of cool utility methods like pollFirstEntry (pull off the first K/V pair), higherMap (view of map that only includes pairs with higher key), etc.
- TreeMap key traversal is deterministic!! The worst bug I encountered in years of programming work was caused by non-determinism in HashMap traversal (you could blame Java's implementation here, I suppose).
- The O(1) vs O(log N) performance difference is minor to the point of being undetectable in every case I've ever encountered.
- When you do something with the data in the map, you often want to sort by key anyway: might as well have the sort taken care of by the data structure.
If it does show up on your profiles, it's easy to reconsider and say "I don't think I'll ever access this in order, after all..." and change it and see if you see a benefit.
I think that premature optimisation applies not only to ease of writing, but even more to ease of debugging.
An unordered map has the narrower interface and generally better performance, so it's much better as the default. Choosing to use an ordered map instead is YAGNI interface bloat that is nearly always unnecessary.
All else equal wrt simplicity, choose the highest performing option that contains the features you need. Dogmatic premature optimization rules are unhelpful. We can apply reasonable thinking, and we should.
And the OP is correct that writing a correct comparison function needed for an ordered map is easier than writing a correct hash function that is properly distributed. So the ordered map is lower effort for that reason alone, although the other properties the OP lists also produce valid reductions of effort.
Now, compacting is an O(n) memory move plus additional calculation to figure out optimal-ish layout.
(Can be amortized, but it's same as amortizing hash table resizing. Optimal layout cannot be decided without profiling, and that's expensive.)
Java itself introduced Objects.hash(Object...) in 1.7 https://docs.oracle.com/javase/7/docs/api/java/util/Objects....
It's never really been an issue at all to implement equals/hashcode, which you're required to do for effectively all Collections-based usage anyway.
But it only needs to have this property for hashes of one particular size, whereas a hash map requires a function that behaves well for a variety of hash sizes. So there's an opportunity for using a cheaper hash function.
Its exactly the same but with fonts and animated transitions.
Could gmail have been built in Oracle forms, how about slack? How about Asana? How about an LMS such as blackboard, moodle, or D2L? Can you name any popular mainstream product that could be built upon and run off the Oracle forms product?
Oracle forms will get you 80% of the way there, and the final 20% will be impossible.
Yes, it could.
Not going to judge whether it's a good idea or not, but it most certainly could be implemented.
I suspect you're not aware just how much capability relational database management systems have.
One of the most insightful design docs I ever read was an exploration by an engineer of how GMail 1.0 could have been implemented with commodity tech and how it'd compare cost wise. The rather sobering conclusion was that it'd have similar functionality and been cheaper to develop/run.
This is a natural match for a key-value store.
In particular, the following KV stores offer hash table-based indexing:
-Berkeley DB 
-Tokyo Cabinet (and its successor, Kyoto Cabinet) 
-Bitcask (used in Riak) 
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
TL;DR: Why? Because you can do range queries and traverse sequential elements faster.
Don't need that? Use hash.
I think ordered indexes are a good default for use in programming languages. They are deterministic and do not have strange corner cases that can be exploited.
E.g. the order when iterating over elements in a hashtable is pretty much random, whereas the order of elements in an ordered tree based data structure is deterministic. That can very easily lead to the output of a program being nondeterministic, e.g. when serializing the contents of a hashtable. This is a frequent cause of compilers having non-deterministic builds.
I like my programs to be deterministic and want to precisely control where randomness enters the execution.
Hash collisions can lead to pathological performance. This can be exploited for DOS attacks, unless the hash data structure in question uses good randomization of the hash function. E.g. the rust hash data structures do a good job with this, but the issue just does not exist for an ordered tree based data structure.
The performance difference is often very small unless having very complex keys or very large sets/maps. A hash based data structure is a valid choice for me once the performance actually matters.
Even though tree-based data structures give you an iteration order that is predictable and useful, the structure itself is still not fully memoryless. For example in a red-black tree if you insert an element smaller than all preexisting elements and then immediately delete the minimum, the tree could be different.
You are right that non-deterministic is not strictly correct for non-salted hash functions. That makes it even more annoying, since it is deterministic enough that you might accidentally rely on the order. It is close enough to nondeterministic since iteration order can change when the hash function changes, but also when some minor internal parameter of the hashtable changes.
> Even though tree-based data structures give you an iteration order that is predictable and useful, the structure itself is still not fully memoryless. For example in a red-black tree if you insert an element smaller than all preexisting elements and then immediately delete the minimum, the tree could be different.
Yes, I am aware and a very big fan of data structures that are actually fully memoryless, such as all kinds of binary tries, radix trees, or just wrapped sorted arrays. The latter are totally underrated, since they have very compact in memory representation (just the elements, single piece of heap) and have very competitive lookup performance.
They of course totally suck when you want to do random single element updates, but then just use something else...
I am going to release an entire collections library based on sorted arrays for rust over Christmas...
PS: It isn't difficult to devise hash tables with path-independent iteration order. You can simply order the keys by their hash code values. See e.g., my implementation of bidirectional linear probing: https://github.com/senderista/hashtable-benchmarks/blob/mast....
My stuff is even simpler. It is just a flat array in memory and should just not be used when you want random single element inserts or deletions. But I find that rather uncommon anyway in many use cases. I made sure that building a new collection from an iterator is fast.
What I do use is a minimum comparison sort that makes very common cases very fast in terms of number of comparisons, and some unsafe stuff to allow in place updates to prevent allocations.
Not quite ready for prime time yet, but you can see the basic ideas being used in this data structure:
You could do a deterministic hash table by using a cryptographic hash function like sha256 and then use a binary trie of the hashes. No need to deal with collisions as far as we know. The hash is expensive, but if you need the hash for something else anyway, this is pretty neat...
I wrote efficient set operations for scala.collection.immutable.HashSet once. Lots of bit-twiddling, which is not as fun on the JVM compared to rust...
Some hash tables that are designed to minimize the potential for DDOS attacks and improve the amortization of work use gradual rehashing (Go's hash table does this), but this is also not ideal for databases because the associated disk accesses are so expensive, and it requires significantly more disk space.
Many real world implementations just don't rehash unless you ask, which makes them pretty inefficient for most use cases.
Hash tables to me aren't a go-to -- they're an optimization I reach for only when I have a real performance reason where I have to use them, and my data is highly predictable so I have confidence how to set them up. But honestly, that just doesn't happen that often. I swear, I think I've used Bloom filters more often than hash tables in my life.
The real question, is why C++ designers chose to prioritize sorted maps (RBTrees) over unsorted maps (Hash Maps).
I don't think it's a matter of speed though. I think it's because RBTrees are safer to use. Things can go really wrong with a hashmap if you have a poor hashing function (worst case search is O(n) vs. O(log(n)) for a RBTree)
Honestly, sorted vectors can often be a good replacement, depending on the workload, if you must have ordered data (this is what boost flat_map uses). All 3 (map, unordered_map, sorted vector) can have their uses, depending on what you are doing with the data.
If you need a better performing hash map, there's always Abseil as well.
 : https://www.reddit.com/r/programming/comments/5pwgtn/hash_ma...
 : https://stackoverflow.com/questions/42588264/why-is-stdunord...
 : https://www.youtube.com/watch?v=ncHmEUmJZf4
Not sure how that general principle really applies or if it's just a quirck my brain came up with, though. If you look at distributed hash tables for instance, they are hash tables on a bus network in some sense, but they are used for search/filter tasks over multiple nodes.
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.
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.
It gets a couple sentences in the post, but prefix searches are key (ha!): a sorted index on (foo, bar, baz) helps not only searches on all three attributes but also foo=x and bar=y or just foo=x. It can also be useful when you want to look things up by a prefix of an individual column: filter to a given day or month using a timestamp index, or filter to errors reported from client version 3.2.x. As a “covering index” it can somewhat help with queries that limit to foo=x and do something with bar (filter on it, return it, sum it, etc.). Finally, it helps with multiple scenarios for aggregation, not only searching: a timestamp index can let you get a count of orders by day, hour, or second without needing to make another temporary table/index.
Often the crucial thing for keeping a DB humming is not getting the last couple percent out of already-fast operations but making sure you don’t have any disastrous queries, so an index being versatile for many kinds of search is especially valuable.
Related to that last point, databases are trying to prepare for queries that haven’t even been written yet, while when you’re coding some algorithm that involves a hashtable, you already know exactly what lookup you’re going to do a few lines later. That on its own is going to push you towards more flexible types of indexing.
(Crossposted from https://lobste.rs/s/68dgox/, where other folks have some good comments.)
I wasn't aware of any obvious way to do the same with two on-disk hash tables. But it appears some databases (MySQL?) do this.
So now my question is how.
Use the same hash function for the two tables to be joined, then loop over buckets, matching corresponding buckets between tables? And then what, treat those subsets similar to a join of two unsorted tables? I guess that's okay as long as each of your hash buckets only has very few things in it. Is there a better way?
Parallel databases also use hash join for performing distributed joins: each node hashes its inputs on the join key to distribute onto the other nodes, so that all inputs with the same join key end up on the same node. Then you can apply one of the hash join algorithms above.
It sounds like you might be saying when two large hash-based tables need to be joined, you're basically starting from scratch in that you're not taking advantage of the existing hash data structure. (At least that's how I interpret "build hash tables", in contrast to somehow using what already exists on disk.)
This sounds pretty slow to me compared to a merge join of ordered lists. There seems to be a lot of I/O (including writes, temp files, and a few passes) whereas with a merge join it's just reads and they're more or less sequential I/O.
So this would be a reason for databases to lean toward ordered storage. But only if disk-based hash joins are as slow as I think they are, which is the part I'm not sure about.
I suspect query optimizers haven’t taken hash indexes into account for joins because they’re so rare in practice, but it’s probably worth considering.
For the batch processing use case, you usually want to be able to do range queries with the interior nodes of the tree in memory and the actual data ending up resident on disk.
For the single-record lookup case (ie serving a user's data to them via a webpage) something like linear hashing actually does have better performance characteristics, although trees are usually good enough.
Most programming tasks work with static datasets because memory is volatile. We are always loading the data from somewhere else and usually just once because reactively updating the in-memory collection is nontrivial to hook up. On the other hand, this is the default for databases.
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.
Also, this can be used as a persistent, on-disk / flash drive data structure or as a hash array mapped trie for HashMap implementations in-memory (Scala or Closure for instance).
For a persistent (both in the sense of functional programming as well as storing on non-volatile disk), this is for instance implemented in SirixDB (https://sirix.io), a temporal data store prototype I'm maintaining and developing :-)
Extendible hashing—a fast access method for dynamic files
Because databases are designed to be efficient at scale. A hash table just doesn't have the functionality that a database with a B-tree variant does.
Hash tables are easier to use on arbitrary data because they don't require Comparator to be defined.
Trees are faster when data is large enough that performance matters.