graham-memcache at ript.net
Thu Nov 17 09:04:45 PST 2005
Fabian Thylmann wrote:
> My guess though is that due to the way to keys are found normally a
> wildcard would slow finding them down a lot, is that correct?
Since memcache uses a hash table internally to store the data (as
opposed to, say, a binary tree of some sort where at least trailing
wildcards would be possible), it would essentially require a sequential
scan of the entire table to find matching entries. This would obviously
be very slow on any large data set. The reason for this is that in a
hash table, keys are decomposed to a value that can be used as an index
into an array of buckets. Only a completely matching key can be used to
find items in the table.
The only way this could happen is either by reimplementing it using some
kind of tree (a splay tree would probably work pretty well for memcache)
so you could at least match only the beginning of the key, or by adding
secondary indexes that are maintained alongside the main index.
More information about the memcached