[openib-general] SA cache design

[Grant Grundler]

On Thu, Jan 12, 2006 at 11:58:28AM -0800, Sean Hefty wrote:
> This is still O(NlogN) operations, which made me look at indexing schemes 
> to improve performance.

I strongly associate "Indexing schemes"  with "judy":
	http://docs.hp.com/en/B6841-90001/ix01.html

The open source project is here:
	http://judy.sourceforge.net/

> The most obvious implementation to me was to store path records in a binary 
> tree sorted by dgid/pkey.  But this isn't very flexible.

"dynamic, associative array" might be overkill too.
I'm not sure how many index's it supports but Judy is definitely
worth looking at for a "simple" implementation.

Perf data I've seen 3-4 years ago indicated that Judy scales
nicely from 0 to several million entries.

grant