Re: half-full btrees and hashtables.
I don't know if that will help you, but a good implementation of
B-Trees was released by Turbo-Power to open source... And alto it does
not uses a very popular language (Delphi and Turbo Pascal) it may help
you getting started.
The link for the implementation is:
--- In firstname.lastname@example.org, Tzahi Fadida <tzahi_ml@f...> wrote:
> Hi guys,
> I am looking on information on the storage complexity of
> btrees and hashtables (or anything with fast access and smaller
> storage space). I am specifically looking for lower worse-cases.
> B is the size of all the data records.
> The data records are arbitrary strings so I don't think there
> is a good hash function.
> The inserts are random (i.e. no bulk loadings).
> The data can be fully retrieved(i.e. no md5 checksums for this).
> How much of B uses a btree that storages all the data records in it.
> How much of B when the btree is half-full.
> The same questions for hashtables (especially for those).
> I know that btrees are usually kept at 67% occupancy when full
> and guarrentee 50% occupancy. i.e. I am guessing that half-full
> the btrees can hold B space and when full it's a lot bigger then B.
> For hashtable I don't know, but I am guessing its close to the same.
> but I can't find info on this.
> In general I think (but can't prove) that all those indices that
> access (such as logarithm in B or less)
> using equality operators must occupy when full around 25% more
> than packed and not indexed. As for half-full, it usually more but
> lot more
> then when completely full.
> WARNING TO SPAMMERS: see at