Loading ...
Sorry, an error occurred while loading the content.
 

Re: half-full btrees and hashtables.

Expand Messages
  • ik_5
    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
    Message 1 of 6 , Apr 16, 2005
      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

      --- In hackers-il@yahoogroups.com, 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
      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
    Your message has been successfully submitted and would be delivered to recipients shortly.