How do disk pointers work?

Question

Suppose I want to store a complicated data structure (a tree, say) to disk. The internal pointers which connect nodes in my data structures are pointers, but I can't just write these pointers to disk, because when I read the data structure back the memory locations will have changed.

So what is the right way to store the pointers on disk? Is the answer as simple as (File, Offset), or is there something that I'm missing? I can intuit how pointers might be converted to (File, offset) pairs, and back again, but are there some subtleties that I should watch out for?

Edit: I should mention that I'm especially interested in how a database would do this internally, for a b-tree. I probably made the question more general than I should have, though I do appreciate the XML-based answers.

Oram

Very similar: #371871 – Scholastic

@dmckee: Not exactly. Though I probably phrased the question in a less than ideal way, I'm interested specifically in how file pointers map to disk pointers and vice versa. And in particular, how databases handle this efficiently and reliably. – Oram

Don't fret. It wasn't a call to close (in part because weren't any really satisfactory answers to 371371), but what do you think "...should accept arbitrarily nested structures, possibly with circular references." means? – Scholastic

Probably that somebody really likes graph theory. – Oram

Answer 1

Your intutuion about (file, offset) pairs is correct.

An important thing to watch out for when storing data on disks is that, disks are slow. So, there are special data structures which have been designed to store "searchable" data on disks. Accessing nodes of a binary search tree stored on disks using (file, offset) pointer would be orders of magnitude slower than accessing them in memory.

If speed of access is important, you'd want to store things which are expected to accessed together, closer together on disks. A couple of data structures used for this are B-tree and B+ tree. Look these up, to find out how to use them. There are complicated caching algorithms used by several applications such as databases, to cache things in memory, so that apps do not need to go to disk to retrieve stuff again and again.

If speed of access is not important, then simply "serializing" data on disk in the form of XML as suggested by Aiden and Darren is good enough.

Edit: If you need more details about how databases store data on disk, you'd need to learn more about database theory. I'd suggest reading up a good book on databases, so that you understand the requirements that drive the disk format. Note that I am mostly referring to relational databases here, but there are other breeds of databases, which have completely different requirements and hence different disk formats. Starting with relational databases is a good thing to do though, since they are most commonly used.

In short a few things that affect relational database disk format are:

1. Disk read/write performance
   
2. Database recovery (in case of corruption)
   
3. Relations between entities
   
4. Garbage collection
   
5. Transactional support
   
6. Primary index
   

Query optimization is an important branch of database theory to optimize disk accesses, for satisfying a query. Hopefully, this will get you started in the right direction.

Closet

+1 for the speed issues. I would add that if your app has an API for accessing trees on-file via a path like "/root/child/child" then you can cache and index these for rapid searching/opening. – Halfon

@Sudhanshu: The Sqlite database would be a good contender to check out the code and see how it is done and is in the public domain. :) – Windburn

+1 @tommieb75: Thanks. Yeah, sqlite is a good place to start. Its important though to go through theory to get a high level view, and look at sqlite for practical inspiration. – Closet

More than what you want to know about BTrees. ;) news.ycombinator.com/item?id=28221612 – Closet

Answer 2

Anyway you like. You could store it as references to other files on-top of a filesystem for each node, or write a filesystem driver that uses block references.

Providing:

1. Your nodes contain references to locations that persist
2. You can know when writing a node what locations to write

You can do it any way you wish. Filesystems are trees that use a disk-based inode system.

You could always use a single file with a header and use byte-offsets stored as unsigned ints or values that map onto ints. inside the file to denote the start of some node ... then have an end-of-record at the end of each node.

You could also use XML files with references to other locations or a single file and XPath/XPointers.

<Node id="someNode">
    <value>...</value>
    <children>
        <child xpath="/node[id=1]" />
        <child xpath="/node[id=29]" />

But this would mean serializing your values into characters if they are just binary blobs (eww) Your value could be a path of a binary chunk just written to a file such as:

<value>/path/to/mappable.bin</value>

Check out anything from XML encapsulation through to filesystems written in C for a whole gamut of tree implementations.

This XML solution might be bloated, but is simple enough if you don't need speed. Just an example of a high-level approach. Tree storage is an age-old problem, with solutions at all levels.

Trees is trees.

Halfon

Answer 3

Binary or Text is the first question

Historically applications used complex binary formats for structured data but the current trend is to define a text-based representation as this produces more developer- and user- friendly files.

XML was created as a portable way to persist and interchange structured data.

If it were me, I would use the XML-like but less clunky YAML.

If the files are likely to get really large then you could do what OpenOffice does and keep them as text-based markup but written directly into a compressed (I think it's zip for OO) archive.

Most languages already have serialization libraries; I'm sure there is some Boost library for C. Typically there are multiple serialization interfaces that use different representations.

If you use a library, XML, or YAML, the links will be implicit in the tree-structured representation. If your data has a more general graph, then whether you use text or binary you may have to normalize links. This is the pointer problem you mentioned. One way to resolve it would be to keep temporary maps that are used when reading or writing the file. That is, you just name every link target, say, A1, A2, A3 ... and then use it as a tag at the destination and as a link name (think href=) at the source.

I would not use file offsets as pointers, it just seems too fragile and naturally it makes sense to use XML or YAML or something else that already exists.

Crescent

Answer 4

Exactly, storing pointers value would be meaningless.

You should create a textual or binary format that will hold the data in a tree structure.
I suggest reading about the Nested Set Model, which is another example about storing tree data structure in a relational database.

For example, this is how your data may be stored:

[meta-data][data]

[meta-data] = [ length ][ list-of-Nested-Set-Model-Locations ] [ list-of-data-records ] = [ lft-#1 ][ rgt-#1 ][ lft-#2 ][ rgt-#2 ] ... [data] = [length][ payload / data-itself ]

This is only an example, and using JSON (recommended) or XML maybe better & easier.

Scandal

Answer 5

Would it be possible to searialize your in-memory tree? This sounds like the common java problem of sending an object over the network. Objects have references to other things, but those pointer address would change once out of the program's address space. Could you serialize your tree to an XML or JSON form?

Ornstead