Results 1 to 6 of 6
  1. #1
    Join Date
    Jan 2006
    Posts
    5

    B+tree implementation questions

    Dear list,

    i don't know if this is a good place for Btree questions, but if anybody of you knows a better place, a mailing list, use group etc, please tell me

    i have implemented a B+tree library for a small database. it's my spare time hobby. It works quite well, but i want to add additional features. two of them are duplicate keys and variable size key length.

    and so far i haven't found information about how to implement them. i have some ideas, but they are not always efficient.

    therefore, if anybody knows about a paper or a web page which discusses these questions, i'm very grateful.

    Thanks,
    Chris

  2. #2
    Join Date
    Feb 2004
    Location
    In front of the computer
    Posts
    15,579
    There are a lot of issues with B-Trees, but those issues are platform specific. In other words, you'll make different choices when implementing on a Palm using forth than you will on a Unix server or a Windows desktop. Without knowing your target, I can't really coach you very well.

    There are a couple of good books on databases that cover B-Trees. One fundamental book would be Donald Knuth's Fundamental Algorithms: Searching and Sorting. Robert Barron did a good one about thirty years ago on database implementations (I don't remember the title, but could find it given a week or two).

    -PatP

  3. #3
    Join Date
    Jan 2006
    Posts
    5
    Hi Pat,

    my programming language is C, but processor architecture and operating system are independent - i use little-endian and as long as the OS is posix-compatible, it should compile everywhere (with minor changes).

    I will have a look for Robert Baron's book. Thanks!

    Chris

  4. #4
    Join Date
    Jan 2006
    Posts
    5
    is it really "barron"? my amazon search didn't find him...

  5. #5
    Join Date
    Feb 2004
    Location
    In front of the computer
    Posts
    15,579
    Ouch... I'm feeling REALLY old now...

    The book I was thinking of is actually Data Structures and Their Implementation. I need to double check to be sure that it has the chapters I was thinking of and that I haven't confused it with another book.

    I'll grab a hot toddy and a bucket of Ben-Gay tonight, and see if I can find my copy! Egad!

    -PatP

  6. #6
    Join Date
    Jan 2006
    Posts
    5
    hi Pat!

    Don't worry - last week i wanted to enter my flat, and the key didn't work. then i discovered that i'm in the first floor, not the second floor, where my flat is. THAT makes you feel old! (and stupid)

    The book of Knuth is a bit too basic - my B+Tree is already working, and i guess my questions about duplicate keys and keys with variable length are a bit too specific. however, if the baron-book has something about these topics, i'll try to get my hands on a copy.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •