Re: B-tree performance

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

On Monday, 2 September 2013 06:28:57 UTC+2, Niklas Holsti  wrote:
> 
> 
> But insertion and deletion are simple and fast in the basic hash-table
> structure, too, as long as the collision sets are small.
> 
Only if the hash-table is large relative to the date. The test data I'm using contains 13,225,167 triples - a real triplestore might have ten times that. The file is nearly 2Gb in size.
> 
> In the traditional hash-table structure, the collision sets are
> implemented as unordered linked lists of objects. You can insert or
> delete any list entry with a few link changes. If you adjust the size of
> the hash table to keep the collision set size bounded by some constant,
> 
I am meaning, as I said, to use a binary tree - a linked list. So collisions will just be further links.

The problem I see is the tree getting too deep, so that it takes too long to find items (as usual the time to add something is less critical than the time to find something). The fewer collisions, the less lookup time, but the more items in the top-level hash table, the shallower the overall structure.