Fast search of guid tables
Posted on 2011-03-21
We are increasingly using guids as keys for objects. Currently the guids are kept in sorted arrays in memory and lookup is done by binary search.
Since guids are widely used I guess the best organisation for fast lookup is thoroughly researched by now. I am looking for a pointer to a good description (on the web) of the best algoritms for this or advice from somebody who has firsthand experience with implementation of this.
My question is: Can we get significantly faster lookup on guids than binary sort for our use (se below)? In that case, what organisation/lookup algorithms would be faster?
Here are some details of our implementation:
It is programmed in C++ (We are not using a DB tool) .
The guid tables will typically be up to 1 million entries.
The guid tables will all be in memory.
The lookup speed is very critical and it is done many times in "inner loops".
The tables are not known at compiletime.
Some tables are fairly stable after first time load.
Some tables are dynamic (delete/insert). Most of the operations will however be add or insert.
The speed of the delete/insert/add administration is not as critical as the lookup speed.
We know in advance which tables are dynamic and which are stable.