4 ms·

I always thought that the main advantage of graph databases is the O(1) lookup instead of the O(log n) lookup in a traditional foreign-key relationship. There i

I always thought that the main advantage of graph databases is the O(1) lookup instead of the O(log n) lookup in a traditional foreign-key relationship. There is no need to search an index, since the pointer already records the location of the adjacent document. On disk, the seeking time would be roughly equivalent if the database is heavily used, since reads/writes would be batched as the disk head moves over the disk, or for other types of drives some similar technique would be used.

lobster_johnson 11y ago
The problem with a "pointer" like this is that you then can't move stuff around as easily. SQL databases frequently reorganize the physical representation of rows to reclaim space used by deleted data, for example. Surely the same would apply to graph/object databases. SQL databases _could_ conceivably optimize foreign key constraints behind the scenes by replacing/augmenting the referencing column with the physical location of the foreign row, but what do you do when the target row moves around in the physical store? You'd have to hunt down all the references and replace them. If anything can point to anything, that could have a cascading effect. You could have conceivably have an indirection here: Instead of pointing to the physical location of another row, you pointed to the physical location of a special intermediate file that itself could contain the physical location. I don't know of any database that uses any tricks like these.
- phpnode 11y ago
  > The problem with a "pointer" like this is that you then can't move stuff around as easily You can, it just requires one further level of pointer indirection. Rather than pointing to the physical location of the data, you store a pointer to an offset in an array of pointers. Alternatively you can point directly if you're prepared to update those pointers when you move things around. Luckily a graph database is ideally suited for this kind of operation because it makes discovering those pointers exceptionally simple and efficient.
  - lobster_johnson 11y ago
    Yes, that was the solution I sketched out in my last paragraph. Do any databases actually do this?
    - phpnode 11y ago
      The array of pointers thing is standard/common but I'm not aware of any which use the features of the graph itself to avoid pointer indirection. Typically the edges are stored in some kind of tree structure anyway so I'd guess that the savings aren't worth the added complexity when the thing does a lot of pointer lookups besides the initial one. But I'm probably going to experiment with it in my own db project.

lobster_johnson 11y ago

The problem with a "pointer" like this is that you then can't move stuff around as easily. SQL databases frequently reorganize the physical representation of rows to reclaim space used by deleted data, for example. Surely the same would apply to graph/object databases. SQL databases _could_ conceivably optimize foreign key constraints behind the scenes by replacing/augmenting the referencing column with the physical location of the foreign row, but what do you do when the target row moves around in the physical store? You'd have to hunt down all the references and replace them. If anything can point to anything, that could have a cascading effect. You could have conceivably have an indirection here: Instead of pointing to the physical location of another row, you pointed to the physical location of a special intermediate file that itself could contain the physical location. I don't know of any database that uses any tricks like these.

phpnode 11y ago
> The problem with a "pointer" like this is that you then can't move stuff around as easily You can, it just requires one further level of pointer indirection. Rather than pointing to the physical location of the data, you store a pointer to an offset in an array of pointers. Alternatively you can point directly if you're prepared to update those pointers when you move things around. Luckily a graph database is ideally suited for this kind of operation because it makes discovering those pointers exceptionally simple and efficient.
- lobster_johnson 11y ago
  Yes, that was the solution I sketched out in my last paragraph. Do any databases actually do this?
  - phpnode 11y ago
    The array of pointers thing is standard/common but I'm not aware of any which use the features of the graph itself to avoid pointer indirection. Typically the edges are stored in some kind of tree structure anyway so I'd guess that the savings aren't worth the added complexity when the thing does a lot of pointer lookups besides the initial one. But I'm probably going to experiment with it in my own db project.