Re: B-tree performance

[Peter Brooks <peter.h.m.brooks@gmail.com>]

On Sunday, 1 September 2013 10:05:27 UTC+2, Niklas Holsti  wrote:
>  
> 
> If for some reason you want to the keep the hash-table small, although
> this leads to many collisions, I suppose you could organize the
> colliding object sets into some kind of keyed containers, for example
> B-trees, but then you should use the actual key to index these
> containers, not the hash-value.
> 
I'm using a tree structure to represent a sparse array because it makes inserts and deletes easier and quicker, and cleaner. I'm using the large hash index to minimise the number of collisions.

If there was a better sparse array algorithm that'd probably suit me better. Then I'd simply hash everything to a 32 bit (or even larger) array index and be done with it. 

With dynamic allocation, memory is used more efficiently. If you use a sparse array, it can grow in size slowly (needing periodic cleaning) because deletions don't delete the location, but simply put the contents to null, and such null entries accumulate.
> 
> 
> I assume your data structures will be in main memory. If some parts are
> in secondary memory (disk files) there are more trade-offs to consider.
> 
I'm hoping to use persistent objects to reduce the extra complications there - using OS paging makes more sense, from a performance point of view, than using files. 

If the persistent objects are shadowed in RAM disc and that's shared over a network, it can make the solution nicely scalable across multiple networked machines.
> 
> Either make up an analytical model (which will of course depend on lots
> of parameters of the problem and processor) or experiment and measure. I
> would do the latter. But it will probably also depend on the pattern of
> accesses. For example, if the accesses have temporal locality, using
> some kind of "move to front" heuristic on the lists of colliding objects
> can help.
> 
Yes, some sort of caching might help, particularly for predicates.