Re: btree on disk

Hello Joel,

Thanks for the hints.

Yes, I am researching on how to design my own file format. Since adjacency
matrix does not scale well, and removals are problematic, I had decided to
use an adjacency list presentation of a graph.

I have tried the b-tree approach, and yes that was real slow.

I need 2 things in main:

a. being able to find things on disk with an id.

b. being able to link things by referencing on some physical id on disk.

    let me explain more on that. lets say we have an edge (a, b) and we put
this somewhere on disk.
    to find vertex b, I dont want to search a hashtable, but rather just
follow a link to b's location on       disk.

Best Regards,

-C.B.


On 7/10/07, Joel Nelson <[email protected]> wrote:
>
> > it otherwords, I have to check if a graph contains a node n, if it does
> not
> > write a new node, and if it does retrieve the node. I need to be able to
> do
> > this very fast. I have tried object oriented dbms, although they worked
> > nicely for graph things, they were very poor at identity search.
> >
>
> Remember what a btree is good at: requiring a minimal number of disk
> accesses to do range queries, e.g. "give me all nodes with a key
> between 54-98"
>
> If you do not need range queries, and you don't need to iterate over
> the nodes in some sorted order, there is no advantage I know of to
> using a b-tree, or any other tree structure.
>
> Instead, it sounds like you already know what exact key value to look
> for (there is no range). In this case, a hash table (and therefore the
> HashFiler) may be a lot faster for you. A hash table can be configured
> so that it almost always finds (or reports that it cannot find) your
> node with 1 disk access, versus a btree which can require 3-5.
>
> Also depending on what you are trying to do with these graphs, there
> are specialized data structures that may work even better than a hash
> table. If you are willing as you said to create your own database, you
> should not be afraid to investigate using your own file format.
>
> Here are some common structures used for storing graphs:
>
> http://en.wikipedia.org/wiki/Adjacency_list
> http://en.wikipedia.org/wiki/Adjacency_matrix
>
> Hope this helps.
>