2.3. B-trees

In this lecture we look at...
[Section notes PDF 159Kb]

2.3.01. Hash tables

  • Used to implement Indicies
  • O(n) access
  • Ordering Key Field (K) as argument to Hash function H()
  • Address H(K) maps to pointer

Hash table example

2.3.02. Tree structure

  • Tree revision
  • Node based
  • Branching nodes/leaf nodes
  • Parent/child nodes
  • Root node
  • Cardinality

Basic tree structure

2.3.03. Multi-level indices

  • Multi-level indices
  • One index indexes another
  • Implemented by multiple hash-tables
  • <H(k),P> pairs
  • (data far right)

Multi-level indices by hash table

2.3.04. Index zipping

  • Collapsing a single index
  • Two columns become one
  • <H(k),P> pairs sequentially stored
  • Common in the Elmasri

Index zipping

2.3.05. B-tree

  • Paritioning structure
  • Each node contains keys & pointers
  • Pointers can be:
    • Node pointers - to child nodes
    • Data pointers - to records in heap
  • Number of keys = Number of pointers - 1
  • Every node in the tree is identical

B tree

2.3.06. B+ trees

  • Similar to B-trees
  • Different types of nodes
    • Branching nodes
    • Leaf nodes
  • Each branching node has:
  • At most U children (max U)
  • At least L children (min L)
  • U = 2L, or U = 2L-1

B+ tree

2.3.07. Properties of B+ trees

  • Balanced
  • All leaf nodes at same level
  • Record search takes same time for every record
  • Partitioning needs to be comprehensive
  • B-tree: a1 < x < a2
  • B+tree: a1 <= x <= a2
  • Why?
    • because all data for partition values must be in the lowest level of the tree

2.3.08. B+ tree operations

  • Insert operation cascades from bottom
  • Rules: node can contain U children (max)
  • Node combine
    • Legal if child nodes contain L children
    • Parent loses one key/paritition value
  • Node split
    • Legal if node contains U children
    • Parent node gains one key/partition value
      • Can cause cascade up tree & rebalancing

B+ tree operations