Concept - B*Trees - NTFS Directory Trees

Home Add Delete

References

Here are some sites that I found helpful whilst writing the B-Tree code.

Basic Terminology

Key

An object bearing data

Leaf

A key with no children

Node

A collection of keys

Order

A node of order n, has a maximum of n-1 keys

Tree

An ordered data structure

Root Node

A node with no parent

Median

The ceil((n-1)/2)th key in a node

Siblings

Two keys in the same node, or two nodes with the same parent

Depth

The number of layers in the tree. Grandparent, parents, children = 3

b-tree

A balanced tree

b+tree

A balanced tree whose nodes are at least 1/2 full

b*tree

A balanced tree whose nodes are at least 2/3 full

Overview

B+Trees

  fixed order
  height balanced
  during add/remove of keys
  minimal disturbance
  pointers downwards only
  

NTFS Trees

      index root
      index allocation
      dummy keys
      data in non-leaf keys
      on-disk pointer only point down

  What we have so far

      ...

  Overview

      ...

  Add Rules

      Find the first key that is larger than the new key
      (this will be a necessarily be a leaf)
      Insert the new key before this key (in the same node)
      While the node is full
	  Split the current node in two
	  Promote the median key to the parent
	  Now consider the parent
      End

  Delete Rules

      Delete the key
      If the key had children
	  Find the successor and move it to this node
	  Now consider the successor's old node
      End
      While the node isn't full enough
	  If a sibling has enough keys
	    steal one
	  Else
	    Combine with one of the sibling
	  End
      End
  

Examples

This is a set of examples covering all the mechanisms for a B+Tree. There are other combinations which are the mirror images of some of the examples.

All the examples have nodes with order 4, i.e a maximum of 4 keys. With higher orders, some other manipulations will be necessary.

In each of the examples, a node (cyan) contains one or more keys (white, named). Each node is terminated with a dummy key (exclamation mark) which is lexicographically higher in any comparisons with normal key names.

How to debug

Here's a picture of flatcap debugging the code using ddd - The Data Display Debugger.

Discussion

A discussion log from #ntfs on IRC.