Results 1 to 8 of 8
  1. #1
    Join Date
    Mar 2007
    Posts
    2

    b+tree and the SQLite

    First things first. My English sucks and I have no knowledge of database design. Good thing is that I'm willing to learn and I would appreciate if you could suggest me some good book to start with.

    I'm designing a file format which is perfectly represented in the form of b+tree. It's ok while the file is in the memory, but I have some serious problems representing the data in the file.

    Before I jump to implement some sort of xml clone or something even worst I would like to know is it possible to use SQLite to implement this? If it's possible how to do that? If I'm asking too much could you give me some pointers where could I find more about it?

  2. #2
    Join Date
    Apr 2002
    Location
    Toronto, Canada
    Posts
    20,002
    if you have no knowledge of database design, how in the world did you ever reach the conclusion that you might want to do this with SQLite?

    try an introductory tutorial on data modelling, e.g. http://www.utexas.edu/its/windows/da.../datamodeling/
    rudy.ca | @rudydotca
    Buy my SitePoint book: Simply SQL

  3. #3
    Join Date
    Jun 2003
    Location
    Ohio
    Posts
    12,592
    If you English sucks, how do you write so well?

    You're English be much gooder then many English posters on these forum.

    They have sent us up the bomb! Make your time!
    If it's not practically useful, then it's practically useless.

    blindman
    www.chess.com: "sqlblindman"
    www.LobsterShot.blogspot.com

  4. #4
    Join Date
    Apr 2002
    Location
    Toronto, Canada
    Posts
    20,002

  5. #5
    Join Date
    Oct 2002
    Location
    Baghdad, Iraq
    Posts
    697
    Quote Originally Posted by sql_wtf?
    First things first. My English sucks and I have no knowledge of database design. Good thing is that I'm willing to learn and I would appreciate if you could suggest me some good book to start with.

    I'm designing a file format which is perfectly represented in the form of b+tree. It's ok while the file is in the memory, but I have some serious problems representing the data in the file.

    Before I jump to implement some sort of xml clone or something even worst I would like to know is it possible to use SQLite to implement this? If it's possible how to do that? If I'm asking too much could you give me some pointers where could I find more about it?
    Hold on a second. I don't want to insult your intelligence, but let's make sure we're all using the terminology correctly.

    Are we talking about a B+ variant of the B-tree or a binary tree?

    To sum up the links, a binary tree is a logical structure, namely a tree with 0, 1 or 2 children at each node. A B-tree (B+tree is a variant of it) is an *implementation* of a logical structure, namely, an ordered map.

    Honestly, given that you don't know anything about database design, I seriously doubt you really want a binary tree. And I know you don't want to implement a B+ tree in SQL Lite (or whatever DBMS) because that's something the DBMS handles for you internally.

    If you want some help assessing your design, explain to me in complete sentences what you're trying to accomplish. No diagrams please, and no cryptic lists of tables and columns.

  6. #6
    Join Date
    Mar 2007
    Posts
    2
    Quote Originally Posted by sco08y
    Hold on a second. I don't want to insult your intelligence, but let's make sure we're all using the terminology correctly.

    Are we talking about a B+ variant of the B-tree or a binary tree?

    To sum up the links, a binary tree is a logical structure, namely a tree with 0, 1 or 2 children at each node. A B-tree (B+tree is a variant of it) is an *implementation* of a logical structure, namely, an ordered map.

    Honestly, given that you don't know anything about database design, I seriously doubt you really want a binary tree. And I know you don't want to implement a B+ tree in SQL Lite (or whatever DBMS) because that's something the DBMS handles for you internally.

    If you want some help assessing your design, explain to me in complete sentences what you're trying to accomplish. No diagrams please, and no cryptic lists of tables and columns.
    Well, I'm not sure about my intelligence or b+tree (yes, the variant of b-tree) anymore . Are you familiar with the concept of two-pane outliner? I need almost the same thing.

    I have a left pane of window in wich I have a tree-view control, user can add/delete/rename child nodes, chiled nodes can have any number of child nodes, which can have .... To the every node user can add/delete some data.

    I'm creating tree view control at the runtime and the control is initialized with data in my file. So, why do you want SQLite? It seems to me that would be convenient, but I don't know is it possible to do that. Yes, I've created a few tables in my life, I do know what is SELECT * FROM,.. but I'm the novice lost in the dark .

    My current starategy is this: 1. run the algorithm which would read from the file and create the structure (some kind of a tree?) 2. run the another algorithm that would from that data structure (tree?) initialize the tree-view control.

    I'm not sure if I'm on the right track, so if you have a better solution please do insult my "intelligence".

  7. #7
    Join Date
    Oct 2002
    Location
    Baghdad, Iraq
    Posts
    697
    Quote Originally Posted by sql_wtf?
    Well, I'm not sure about my intelligence or b+tree (yes, the variant of b-tree) anymore . Are you familiar with the concept of two-pane outliner? I need almost the same thing.

    I have a left pane of window in wich I have a tree-view control, user can add/delete/rename child nodes, chiled nodes can have any[my emphasis] number of child nodes, which can have .... To the every node user can add/delete some data.
    So you want something that looks like folder view in Windows explorer.

    But if you want any number of child nodes, you're not dealing with a binary tree. It's just a tree.

    Let me point out that you probably shouldn't implement an arbitrarily nested tree. It's a terrible way to do a GUI. When was the last time you dug into a Windows help file to find something? Or tediously searched through folders? I haven't done it ever since Spotlight came out on the Mac and Google Desktop came out for Windows.

    I haven't seen proper research on it, but from experience I'd say that the user shouldn't be exposed to more than 5 levels of nesting.

    And if you take my advice, you don't need a tree in SQL. You can just have fields like cat1, cat2, cat3, cat4.

    But if you're dead set on an infinitely expandable tree... Here's one way of declaring a tree in SQL:

    Code:
    CREATE TABLE nodes (
        id         INTEGER PRIMARY KEY,
        parent     INTEGER NOT NULL REFERENCES nodes(id) 
            CHECK((id = 0 AND parent = 0) OR (id <> 0 and id <> parent)),
        payload    SOME_TYPE,
        payload2   SOME_TYPE,
        ...
    )
    id is a number for the node. Since it uniquely identifies the node, it's the primary key. You can have other candidate keys, if necessary.

    I arbitrarily picked 0 to be the "root" node.

    parent identifies the node directly above this node, except for the root node which simply links back to itself. To make this work, parent has three constraints.

    1. It can't be null. Every node has to have a parent.
    2. It has to refer to a real node. The "REFERENCES" clause is shorthand for declaring a foreign key constraint. In this case, it's a self-referential constraint.
    3. One of these two statements are true: this is the root node and parent refers to itself, *or* it's not the root node and its parent is some other node.

    This is a start but it's not a perfect implementation. You could still create a circular system like this:

    Code:
    INSERT INTO nodes VALUES (0, 0)
    INSERT INTO nodes VALUES (1, 0)
    INSERT INTO nodes VALUES (2, 1)
    INSERT INTO nodes VALUES (3, 2)
    UPDATE nodes SET parent = 3 WHERE id = 1
    There are different ways to fix this, depending on what functionality you need.

    Actually working with the tree is pretty easy because the DBMS takes care of allocation and deallocation. It helps to learn how to write stored procedures and triggered procedures.

  8. #8
    Join Date
    Apr 2002
    Location
    Toronto, Canada
    Posts
    20,002
    Quote Originally Posted by sco08y
    I haven't seen proper research on it, but from experience I'd say that the user shouldn't be exposed to more than 5 levels of nesting.
    that is so cool, sco08y, very few people have ever come out and said that

    i take the same position in this article: Categories and Subcategories

    i disagree about the root node having a parent of 0 -- i feel it should be NULL

    with a parent of 0, you will never get the FK declared properly
    rudy.ca | @rudydotca
    Buy my SitePoint book: Simply SQL

Posting Permissions

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