How are binary trees represented on disk

Question

Assume I have a word document, the contents in it are stored on the disk as bits. Nothing so complex here. When the word processor reads those bits, it just knows how to display on screen.

But what about binary trees. They are just not data, they have route node, child nodes. How are they actually represented on disk?

I tried searching using this term "binary trees representation on disk". But I didn't find anything useful.

Let me know if I am not clear

Update:
I was looking for details on how actually they are stored on disk. Given this simple binary tree:

Any data is stored in bits on disk. How are these stored?

Answer 1

This may not be an exact answer but some information of interest related to your question

Other answers have mentioned various ways in which the binary data structure can be represented and you might want to use one of them but mostly when using databases the Adjacency List Model and Nested Set Model are used for representing Binary Trees.

Binary Trees are mostly not used for storing data on disk and some alternatives are usually preferred.If you are interested in optimized data access, search,insertion and deletion on disk then you may want to consider these alternatives

B-Tree data structure is one of the alternatives used for storage on disk.It provides search, sequential access, insert, and delete operations in logarithmic time and is optimized for disk storage.

B-Tree data structure was created by Rudolf Bayer and Ed McCreight in 1972 to overcome a shortfall of Binary Tree i.e. using too many disk reads.B-Tree reduces the number of disk reads by allowing more keys in a single node ( typically making a B-tree node as large as the sector minimizes the number of access times).

SQL Server uses a further optimized extension of B-Tree data structure known as B+Tree in which only the leaf nodes hold the actual data and the rest of the nodes are pointers.

According to Wikipedia B+Trees are also used for storing directory structures by some filesystems:

The ReiserFS, NSS, XFS, JFS, ReFS, and BFS filesystems all use this type of tree for metadata indexing; BFS also uses B+ trees for storing directories. NTFS uses B+ trees for directory and security-related metadata

Update How will a tree be represented as bits on the disk?

Trees can be represented by using static data structures like arrays in a fashion similar to this,consider each row tag as an array

//Node A can be represented as 

[row 1][node A data in bits][separator bits]
[pointer to B i.e row 2][separator bits]
[pointer to C i.e. row 3][row1end]

//Node B can be represented as

[row 2][node B data in bits] [separator bits]
[no child flag][separator bits][no child flag][row2end]

//Node C can be represented as 

[row 3][node C data in bits] [separator bits]
[no child flag][separator bits][no child flag][row3end]

I'd recommend studying some file formats so that you know how to represent logical data in a file, this also might be helpful

dcs.gla.ac.uk/Keith/Chapter.4/Ch.4.html

Answer 2

There are many ways to represent trees, each with their own set of advantages and disadvantages.

Here's an incomplete list:

• Use any graph representation, e.g.

  • adjacency matrix,
  • incidence matrix,
  • adjacency list,
  • linked nodes,

  potentially adding a label for the root (if you have one).

• An array, listing nodes level by level (see e.g. heaps).

• Post- and pre-order sequence (together).

For each of these conceptual representations, there are many ways to implement it memory. For example, you can store adjacency matrices

• row by row,
• colum by column,
• augmented with pointers to skip (long) stretches of zeroes,
• partially (e.g. for diagonal matrices),
• implicitly as product of smaller matrices,

and so on.

Basically, you pick (or invent) a representation and an implementation that has performance characteristics that match the needs at hand.

---

That all said, the most standard representation of binary trees (unless you're looking at heaps), in the absence of contraindicating requirements, are probably linked nodes. It's what you get if you define binary trees similar to this:

type BinaryTree<Value>:
    Leaf
|   Node(BinaryTree, BinaryTree)

Note that this is, essentially, a specialized form of adjacency lists.

A natural implementation would be just the value for leaves, and a value with two pointers for inner nodes. A pointer to the (a) root would represent the (a) whole (sub)tree. How to arrange these in memory is, of course, yet another design decision (maybe deferred to automatic heap management).

Answer 3

There is no standard way to represent data structures of this kind.

One approach could be to sequentially write the content of every node during a inorder traversal, together with information aboud the tree structure.

I guess (this needs to be checked) that two bits indicating if a node has left and right children is enough to reconstruct correctly while reading back.

---

Note that it some applications, you needn't keep the original tree structure but only the content: for instance for a balanced search tree, you can just build a new tree from the keys.

Answer 4

How would you locate your word document?

By storing the location of the "word file" somewhere in an index which again gets stored somewhere, this structure itself represent a tree

For your ans,suppose you store the location of files("C:/abc/def/a.doc") in your "word document" and those files are also "word documents" which stores location of another files and so on, this is how trees are stored,however instead of file format they store memory location of other node and so on.