B-Trees An NTFS index sort attributes into a tree, specifically a B-tree. A tree is a group of data structures called nodes that are linked together such that there is a head node and its branches out to the other nodes. Consider Figure 11.13(A), where we see node A on top and it links to nodes B and C. Node B links to nodes D and E. A parent node is one that links to other nodes, and a child node is one that is linked to. For example, A is a parent node to B and C, which are children of A. A leaf node is one that has no links from it. Nodes C, D, and E are leaves. The example shown is a binary tree because there are a maximum of two children per node. Figure 11.13. Examples of A) a tree with 5 nodes and B) the same tree that is sorted by the node values FIG- 11.3 Trees are useful because they can be used to easily sort and find data. Figure 11.13(B) shows the same tree as we saw on the left side, but now with values that are assigned to each node. If we are trying to look up a ...
Comments