Storage model

  • fixed memory per process
    • no sharing
  • Able to lock/unlock a disk page

Concurrent Issue

  • Process A insert 9
  • Process B search 15
  • Process B goes to old y node => 404 not found

two nodes, since they are joined by a link pointer, are functionally essentially the same as a single node until the proper pointer from their father can be added

  • Add link pointer first when creating new node
  • Normal search, if greater than current node max => follow link

Insert (Splitting node)

  • Splitting node a into a' and b'

Delete

  • Allow leaf nodes with less than k entries
  • (Don’t even need to modify non-leaf nodes)
  • Lock whole tree to reorganize if too many deletions