If both are well designed and programmed. Does B -tree have any advantages for an in-memory database compared to Hash if no range query is needed?

CodePudding user response：

Not only range searches, B-tree (or a variant like B ) can also accommodate partial key searches (i.e. where you know the prefix but not the whole key value), sorted traversal, and easily allow duplicates (hash indexes customarily enforce uniqueness).

Hash index can potentially use less memory (b-trees always have empty space).

Hash tables can be allocated statically (size doesn't change) or dynamically. Static is best if you know how many key values are to be stored with reasonable accurateness. Dynamically allocated hash tables will have wasted space unless/until the new buckets are filled up. B-trees naturally grow as needed.

If a hash table is too small or the hash algorithm is inferior, there will be collisions that require chaining. That will increase the lookup and insertion time. Choosing the best hash algorithm has some dependency on the type of data being indexed, therefore it's virtually impossible to have a single generic hash algorithm that is optimal for everything. B-trees don't have this issue.