Subject: half-full btrees and hashtables.

From: Tzahi Fadida <[email-masked]>
Date: Fri, 15 Apr 2005 14:19:47 +0200

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 have
fast
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 not a
lot more
then when completely full.

Regards,
	tzahi.

WARNING TO SPAMMERS:  see at
http://members.lycos.co.uk/my2nis/spamwarning.html

---

From: Arik Baratz <[email-masked]>
Date: Sat, 16 Apr 2005 18:32:39 +0300

On 15/04/05, Tzahi Fadida <[email-masked]> wrote:
[snip]
> but I can't find info on this.

A hash table has an AVARAGE O(1) on lookups and insertions, as long as
you follow some rules.

There is a relationship between the avarage seek time for a hash and
the amount of free space in the hash table. I don't remember the
formula, but a 80% full hash table has an avarage of 1.1 accesses per
search or insert.

The solution to maintaining a hash table with 80% or less occupancy is
rehashing when the hash table gets too big. Rehashing takes o(n), but
if you avarage it over time and rehash to a table twice as large every
time it crosses the 80% mark, you need an o(log n) rehashes times o(n)
per rehash, so it gives you a reasonable o(log n) for insertions,
leaving searches at o(1). Occupancy fluctuates between 40% to 80%,
which is IMHO very reasonable, considering the benefits. Also, hashes
are usually very low on the constant memory consumption per entry,
unlike B+ trees (with the awful lots of links to maintain).

Unless you are doing this as a CS excercise, in which case go away
now, there are no 'arbitary strings'. The worst case for a hash's
lookup or insert (rehashes aside) is o(n), but in the real world this
doesn't really happen if you have any sense at all in choosing your
hash function.

-- Arik

---

From: Tzahi Fadida <[email-masked]>
Date: Sun, 17 Apr 2005 01:41:13 +0200

The question is, what is the overhead in space of using a hashtable as
opposed
to not using and index at all. 
I already know that a hashtable is fast.
I don't believe that using a hashtable is completely free in trems of
space overhead.

The problem I am having is that the data is exponential in the input and
thus the data
takes a lot of space which some systems don't have. Even so, some
systems would have
enough space for it and for them I would like to use an index. However,
I have to know
how much additional space the index would require.

From what you say a hashtable usually does not go beyond 80% occupancy
(probably 
because its not possible to continue adding and the need to extend the
index or move it
or whatever). This means that the space I will need is dataSize*1.25
which is
what I now corraborate from ramakrishtan book.

Regarding the hash function, and arbitrary. What I mean is that this is
a function that
would work in a database on whatever a client would want to put in the
tables so aside
from a hash function on arbitrary strings I doubt I can predict a good
one without knowing
what is the data.

10x.
Regards,
	tzahi.

> -----Original Message-----
> From: [email-masked] 
> [mailto:[email-masked]] On Behalf Of Arik Baratz
> Sent: Saturday, April 16, 2005 5:33 PM
> To: [email-masked]
> Subject: Re: [hackers-il] half-full btrees and hashtables.
> 
> 
> 
> > 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.
> > 
> A hash table has an AVARAGE O(1) on lookups and insertions, 
> as long as you follow some rules.
> 
> There is a relationship between the avarage seek time for a 
> hash and the amount of free space in the hash table. I don't 
> remember the formula, but a 80% full hash table has an 
> avarage of 1.1 accesses per search or insert.
> 
> The solution to maintaining a hash table with 80% or less 
> occupancy is rehashing when the hash table gets too big. 
> Rehashing takes o(n), but if you avarage it over time and 
> rehash to a table twice as large every time it crosses the 
> 80% mark, you need an o(log n) rehashes times o(n) per 
> rehash, so it gives you a reasonable o(log n) for insertions, 
> leaving searches at o(1). Occupancy fluctuates between 40% to 
> 80%, which is IMHO very reasonable, considering the benefits. 
> Also, hashes are usually very low on the constant memory 
> consumption per entry, unlike B+ trees (with the awful lots 
> of links to maintain).
> 
> Unless you are doing this as a CS excercise, in which case go 
> away now, there are no 'arbitary strings'. The worst case for 
> a hash's lookup or insert (rehashes aside) is o(n), but in 
> the real world this doesn't really happen if you have any 
> sense at all in choosing your hash function.
> 
> -- Arik
> 
> 
>  
> Yahoo! Groups Links
> 
> 
> 
>  
> 
> 
> 
>

---

From: Arik Baratz <[email-masked]>
Date: Sun, 17 Apr 2005 02:02:12 +0300

> I don't believe that using a hashtable is completely free in trems of

Okay. A hash table can be as big as your data. BUT, for efficiency
reasons you want to maintain it at only 80% full (beyond that the
searches become considerably slower).

If yu build it right, every entry in the hash table may be as small as
a pointer in the target architecture.

> how much additional space the index would require.

An index, as a rule, needs approximately n/k nodes, k being the number
of leaves in the last level of the tree, if I'm not mistaken here.
This is o(n) space, like a hash table, but a higher real-world
constant.

> what I now corraborate from ramakrishtan book.

Yes, it doesn't go beyond 80%, but NOT because of some intrinsic
limit. It CAN go to the full 100%, but beyond 80% the avarage cost of
searching the hash table increases considerably. That's why you set an
artificial limit at around 80% and rehash when you get there.

> from a hash function on arbitrary strings I doubt I can predict a good

Well, if they are text strings you have good hash functions for these,
and even automatic hash function generators that go over a sample set
and generate a hash function.

-- Arik

---

From: Tzahi Fadida <[email-masked]>
Date: Sun, 17 Apr 2005 03:16:01 +0200

> > opposed to not using and index at all.
> Okay. A hash table can be as big as your data. BUT, for 
> efficiency reasons you want to maintain it at only 80% full 
> (beyond that the searches become considerably slower).

define slow. see below.

> 
> If yu build it right, every entry in the hash table may be as 
> small as a pointer in the target architecture.
> 
> > The problem I am having is that the data is exponential in 
> the input 
> > and thus the data takes a lot of space which some systems 
> don't have. 
> > Even so, some systems would have
> An index, as a rule, needs approximately n/k nodes, k being 
> the number of leaves in the last level of the tree, if I'm 
> not mistaken here. This is o(n) space, like a hash table, but 
> a higher real-world constant.

You misunderstood me. The data will prefferably be in the index to save
space.
if my data will take 2 times its size it would never fly, i.e. it won't
fit in the storage space.

> > (probably because its not possible to continue adding and 
> the need to 
> > extend the index or move it
> Yes, it doesn't go beyond 80%, but NOT because of some 
> intrinsic limit. It CAN go to the full 100%, but beyond 80% 
> the avarage cost of searching the hash table increases 
> considerably. That's why you set an artificial limit at 
> around 80% and rehash when you get there.

Well, a 100% occupancy is an absurdity since it takes a similar space to
the
size before the index then its similar to a sorted table,
which I am sure is hard to maintain and you don't need an index for
that.
This is why I am saying that if you want to have a useful index and by
useful
I mean the search/addition would take no more then a 
c*log(n)  where c = constant of some kind,
you need to spend around 25% space more then what you spend without an
index.

> 
> > Regarding the hash function, and arbitrary. What I mean is 
> that this 
> > is a function that would work in a database on whatever a 
> client would 
> > want to put in the tables so aside
> Well, if they are text strings you have good hash functions 
> for these, and even automatic hash function generators that 
> go over a sample set and generate a hash function.

Well, it seems logical. however, those generators will have to do that
on the fly without
touching the storage since there are many additions in my potential
index.

---

From: "ik_5" <[email-masked]>
Date: Sat, 16 Apr 2005 09:00:37 -0000

Hi,

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:
http://sourceforge.net/projects/tpbtreefiler/

Regards,

Ido