Protcol Additions

[Graham Batty]

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?
>
> Fabian


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.

Graham.