3
$\begingroup$

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:

enter image description here

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

$\endgroup$
  • $\begingroup$ Does your machine (model) have pointers? If so, it should be immediate. $\endgroup$ – Raphael Aug 13 '17 at 18:21
  • 1
    $\begingroup$ I'm not sure why you're prepared to take it for granted that something as complex as a Word document can be stored on disk as "bits" which the processor "just knows how to display" but you're not OK with applying the same argument to something simple such as a binary tree. Ultimately, though, the answer is "However the programmer decides to." $\endgroup$ – David Richerby Aug 13 '17 at 19:12
  • 3
    $\begingroup$ Ironically, Word documents are trees these days. $\endgroup$ – Raphael Aug 13 '17 at 20:32
  • 1
    $\begingroup$ @TheGameiswar , they will be represented by using static data structures like arrays in a fashion similar to this, Node A will 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 will be represented as [row 2][node B data in bits] [separator bits][no child flag][separator bits][no child flag][row2end], Node C will be represented as [row 3][node C data in bits] [separator bits][no child flag][separator bits][no child flag][row3end] $\endgroup$ – Romantic Electron Aug 16 '17 at 17:36
  • 1
    $\begingroup$ @TheGameiswar I have updated my answer . 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 $\endgroup$ – Romantic Electron Aug 16 '17 at 17:58
7
+50
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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).

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Excellent,thanks for the info on two bits for left/right.Gave me some clue to visualize $\endgroup$ – TheGameiswar Aug 13 '17 at 18:12
  • 1
    $\begingroup$ "There is no standard way to represent data structures of this kind." -- I don't think that's true; there are probably several such ways. $\endgroup$ – Raphael Aug 13 '17 at 18:20
  • 2
    $\begingroup$ Yea, such as there being multiple standard ways to represent graphs (adjacency matrix, adjacency lists, incidence matrix, ...) with different properties. Oh, wait, all these would work for trees as well! $\endgroup$ – Raphael Aug 13 '17 at 18:23
  • 2
    $\begingroup$ @YvesDaoust I think several decades of literature would disagree with you. It's abundantly clear what an adjacency matrix is; you can choose between row or column oriented storage (the former being the default), but that's about it. Note that this site is unconcerned with what is considered standard in programming libraries; we are about concepts. $\endgroup$ – Raphael Aug 13 '17 at 18:36
  • 1
    $\begingroup$ @YvesDaoust CLRS, chapter 12 (in 3rd ed): linked "structs". Mehta/Sahni, section 3.2. TAOCP sections 2.3.2 and 2.3.3. Yes, these things are not always programmer-ready, but that's not the goal of CS either. (Note that disk vs memory does not make a difference in (classic) CS, most of the time.) $\endgroup$ – Raphael Aug 13 '17 at 20:31
-1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This answer is a bit vague. What do you mean by "memory location"? The trees are supposed to be stored on disk. Are they stored by disk location? $\endgroup$ – Yuval Filmus Aug 22 '17 at 9:16
  • $\begingroup$ memory location here means pointers $\endgroup$ – Aditya Agarwal Aug 22 '17 at 11:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.