         address = parseInt match[1], 10
         @nextAddress = address + 1 if address > @nextAddress
 
-  # TODO Very soon.
   close: (_) ->
-#
-#
-# A branch page file contains a single object that includes the array of page
-# addresses that reference the branch page's children.
-#
-# The branch page file also stores a penultimate flag, and the address of the
-# next sibling of the branch
-# page.
-# The keys associated with the child addresses are not stored in the
-# branch page.
-#
-# Put another way, each branch element in a branch page represents a leaf page.
-# The leaf pages are sorted by the tree collation. The object value used to sort
-# the branch page is first element in the sorted leaf page.
-#
-# TODO Okay, what? I'm forgetting that I need the addresses to inner tiers as
-# well as to leaf tiers, both, when the tier is not penultimate. Descending is
-# not going to work, that is going to load the entire tree into memory quickly.
-#
-# Hmm... Maybe not. Tree four deep means loading only a particular path. It
-# ensures that we read lock our way down the tree to get our record. Although, I
-# believe I thought long and hard about this, and jumping down to the leaves
-# wasn't a problem.
-#
-# We only need to store the sorted array of the leaf tier addresses in our
-# branch tier, since we can obtain the object used to collate the address
-
-  # Link tier to the head of the MRU list.
-  link: (entry) ->
-    next = @head.next
-    entry.next = next
-    next.previous = entry
-    @head.next = entry
-    entry.previous = @head
-    entry
-
-  # Unlnk a tier from the MRU list.
-  unlink: (entry) ->
-    { next, previous } = entry
-    next.previous = previous
-    previous.next = next
-    entry
-
-  allocateLeaves: (addresses, right) ->
-    address = @nextAddress++
-    @cache[address] = @link
-      leaf: true
-      address: address
-      addresses: addresses
-      cache: {}
-      right: right
-      io: new LeafIO @filename address
+
+  # TODO Ensure that you close the current tier I/O. Also, you must also be very
+  # much locked before you use this, but I'm sure you know that.
+
+  # ### Concurrency
+  #
+  # The b-tree must only be read and written by a single Node.js process. It is
+  # not suitable for use with multiple node processes, or the cluster API.
+  #
+  # Although there is only a single thread in a Node.js process, the b-tree is
+  # still a concurrent data structure. Instead of thinking about concurrency in
+  # terms of threads we talk about concurrent *descents* of the b-tree.
+  #
+  # When we search the tree or alter the tree, we must descend the tree.
+  #
+  # Decents of the b-tree can become concurrent when descent encounters a page
+  # that is not in memory. While it is waiting on evented I/O to load the page
+  # files, the main thread of the process can make progress on another request
+  # to search or alter the b-tree, it can make process on another descent.
+  #
+  # This concurrency keeps the CPU and I/O loaded.
+  #
+  # ### Locking
+  #
+  # Locking prevents race conditions where an evented I/O request returns to to
+  # find that the sub-tree it was descending has been altered in way that causes
+  # an error. Pages may have split or merged by the main thread, records may
+  # have been inserted or deleted. While evented I/O is performed, the sub-tree
+  # needs to be locked to prevent it from being altered.
+  #
+  # The b-tree is locked page by page. We are able to lock only the pages of
+  # interest to a particular descent of the tree.
+  #
+  # Futhermore, the b-tree destinguishes between shared read locks and exclusive
+  # write locks. Multiple descents can read a traverse that is read locked, but
+  # only the descent that holds an exclusive write lock can traverse it or write
+  # to it.
+  #
+  # Of course, Node.js doesn't have the concept of mutexes to protect critical
+  # sections of code the way that threaded programming platforms do. There are
+  # no standard read and write lock APIs for use to use.
+  #
+  # Nor do we use file system locking.
+  #
+  # Instead, we simulate locks using callbacks. A call to `lock` is an evented
+  # function call that provides a callback. If the `lock` method can grant the
+  # lock request to the caller, the lock method will invoke the callback.
+  #
+  # If the `lock` method cannot grant the lock request, the `lock` method will
+  # queue the callback into a queue of callbacks assocated with the page. When
+  # other descents release the locks that prevent the lock request, the lock
+  # request callback is dequeued, and the callback invoked.
+  #
+  # The locking mechanism is a writer preferred shared read, exclusive write
+  # lock. If a descent holds an exclusive write lock, then all lock requests by
+  # other descents are blocked. If one or more descents hold a shared read lock,
+  # then any request for an exclusive write lock is blocked. Any request for a
+  # shared read lock is granted, unless an exclusive write lock is queued. 
+  #
+  # The locks are not re-entrant.
+  #
+  # #### Lock
+
+  #
+  lock: (exclusive, address, leaf, callback) ->
+    # We must make sure that we have one and only one page object to represent
+    # the page. We the page object will maintain the lock queue for the page. It
+    # won't due to have different descents consulting different lock queues.
+    # There can be only one.
+    #
+    # The queue is implemented using an array of arrays. Shared locks are
+    # grouped inside one of the arrays in the queue element. Exclusive locks are
+    # queued alone as a single element in the array in the queue element.
+    if not page = @cache[address]
+      @cache[address] = page =
+        @link
+          leaf: leaf
+          address: address
+          cache: {}
+          addresses: []
+          locks: [[]]
+
+    # If the page needs to be laoded, we must load the page only after a lock
+    # has been obtained. Loading is a read, so we can load regardless of whether
+    # the lock is exclusive read/write or shared read.
+    if page.loaded
+      lock = callback
+    else
+      lock = (error, page) =>
+        if error
+          callback error
+        else if page.loaded
+          callback null, page
+        else if leaf
+          @readLeaves page, callback
+        else
+          @readBranches page, callback
+
+    # The callback is always added to the queue, even if it is not blocked and
+    # will execute immediately. The array in the queue element acts as a lock
+    # count.
+    #
+    # If the callback we add to the queue is added to the the first queue
+    # element is executed immediately. Otherwise, it will be executed when the
+    # preceeding queue elements have compeleted.
+    #
+    # When an exclusive lock is queued, an empty array is appended to the queue.
+    # Subsequent read lock callbacks are appened to the array in the last
+    # element. This gives exclusive lock callbacks priority.
+    locks = page.locks
+    if exclusive
+      throw new Error "already locked" unless locks.length % 2
+      locks.push [ lock ]
+      locks.push []
+      if locks[0].length is 0
+        locks.shift()
+        lock(null, tier)
+    else
+      locks[locks.length - 1].push lock
+      if locks.length is 1
+        lock(null, tier)
+
+  # #### Unlock
+
+  # When we release a lock, we simply shift a callback off of the array in the
+  # first element of the queue to decrement the lock count. We are only
+  # interested in the count, so it doesn't matter if the callback shifted by the
+  # descent is the one that it queued.
+
+  #
+  release: (tier) ->
+    locks = tier.locks
+    running = locks[0]
+    running.shift()
+    say { locks }
+    if running.length is 0 and locks.length isnt 1
+      locks.shift()
+      @resume tier, locks[0] if locks[0].length
+
+  # We call resume with the list of callbacks shifted off of a pages lock queue.
+  # The callbacks are scheduled to run in the next tick.
+  resume: (page, continuations) ->
+    process.nextTick =>
+      for callback in continuations
+        callback(null, page)
+      
+  upgrade: (tier, _) ->
+    @release tier
+    @lock true, tier.address, false, _
+
+# Descent of a tree.
+
+#              
+class Mutation
+  # The constructor always felt like a dangerous place to be doing anything
+  # meaningful in C++ or Java.
+  constructor: (@strata, @object, @key, @operation) ->
+    @io         = @strata._io
+    @options    = @strata._options
+
+    @parent     = { operations: [], locks: [] }
+    @child      = { operations: [], locks: [] }
+    @exclusive  = []
+    @shared     = []
+    @pivots     = []
+
+    { @extractor, @comparator } = @options
+
+    @key        = @extractor @object if @object? and not key?
 
   # Going forward, every will story keys, so that when we encounter a record, we
   # don't have to run the extractor, plus we get some caching.

      locks.shift()
      true
    false

# ### B-Tree Structure
#
# We call page of the b-tree, ah, maybe we stop using the word tier, start using
# the word page, because we're not going to have to reduce the ambiguity with
# some sort of subdivided binary file structure.
#
# NOTE Come back and look at this. It is succinct.
#
# There are two types of pages. Branch pages and leaf pages.
#
# Leaf pages store the records. They maintain the collation
#
# Leaf pages are all uniformly the same.
#
# ### Leaf Tier Files
#
# A leaf tier maintains an array of file positions called an address array. A
# file position in the address array references a record in the leaf tier file
# by its file position. The addresses in the address array are sorted by the
# the sort order of the referenced records according to the sort order of the
# b-tree.
#
# A leaf tier file contains JSON objects, one object on each line.
#
# There are three types of objects in a leaf tier file, insert objects, delete
# objects, and address array objects.
#
# An insert object contains a *record* and the index in the address array where
# the record's address would be inserted to preserve the sort order of the
# address array.
#
# Beginning with an empty array and reading from the start of the file, the leaf
# tier address array is reconstituted by reading the object at the current
# position in the file, then inserting the position of the current object into
# the address array at the index in the insert object.
#
# We record a deletion by appending a delete object. A delete object contains
# an index in the address array that should be deleted. When reading the leaf
# tier from the start of the file, we insert an address into the address array
# when we encounter an insert object, and we delete an address when we encounter
# a delete object.
#
# On occasion, we can store an address array object, An address array object
# contains the address array itself.  We store a copy of a constructed address
# array object in the leaf tier file so that we can read a large leaf tier file
# quickly.
#
# When we read a leaf tier file, if we read from the back of the file toward the
# front, we can read backward until we find an address array object. Then we can
# read forward to the end of the file, applying the inserts and deletes that
# occured after we wrote the address array object. 
# 
# When a leaf tier file is large, stashing the constructed address array at the
# end means that the leaf tier can be loaded quickly, because we will only have
# to read backwards a few entries to find a mostly completed address array. We
# can then read forward from the array to amend the address array with the
# inserts and deletes that occured after it was written.
#
# Not all of the records will be loaded when we go backwards, but we have their
# file position from the address array, so we can jump to them and load them as
# we need them. That is, if we need them, because owing to binary search, we
# might only need a few records out of a great many records to find the record
# we're looking for.
#
# Over time, a leaf tier file can grow fat with deleted records &mdash; an
# insert object and a subsequent delete object. We vacuum a leaf tier file by
# writing it to a new leaf tier file.

# `LeafIO` &mdash; Keeps track of a file descriptor opened for append, and the
# append file position. The `LeafIO` class does *not* contain all methods
# relating to leaf tier file I/O. You can find more leaf tier file methods in
# the `IO` class below.
#
# TODO Rename `RecordIO`.
class LeafIO
  # Construct a leaf file tier writer for the given file name.
  constructor: (@filename) ->
    @length = 1024

  # #### Leaf Tier File Object Format
  #
  # Each leaf tier object is a JSON array. The first element of the array is an
  # integer.
  #
  # If the integer is greater than zero, it indicates an insert object.  The
  # integer is the one based index into the zero based address array, indicating
  # the index where the position of the current insert object should be
  # inserted. The second element of the leaf tier object array is the record
  # object.

  # Write an insert object.
  writeInsert: (object, index, _) ->
    @_writeJSON [ index + 1, object ], _

  # If the integer is less than zero, it indicates a delete object. The absolute
  # value of the integer is the one based index into the zero based addrss
  # array, indicating the index of address array element that should be deleted.
  # There are no other elements in the leaf tier object array.

  # Write a delete object.
  writeDelete: (index, _) ->
    @_writeJSON [ -(index + 1) ], _
  
  # If the integer is zero, it indicates an address array object. The integer
  # value of zero is used only as an indicator. The second element is the
  # address of the leaf tier to the right of current leaf tier. The third
  # element of the leaf tier object array is the address array.

  # Write an address array object.
  writeAddresses: (right, addresses, _) ->
    @_writeJSON [ 0, right, addresses ], _

  # Append an object to the leaf tier file as a single line of JSON.
  _writeJSON: (object, _) ->
    @fd           or= fs.open @filename, "a+", 0644, _
    @position     or= fs.stat(@filename, _).size

    json            = JSON.stringify object
    position        = @position
    length          = Buffer.byteLength(json, "utf8")
    buffer          = new Buffer(length + 1)
    offset          = 0

    # Write JSON and newline.
    buffer.write json
    buffer[length] = 0x0A

    # Write may be interrupted by a signal, so we keep track of how many bytes
    # are actually written and write the difference if we come up short.
    while offset != buffer.length
      count = buffer.length - offset
      written = fs.write @fd, buffer, offset, count, @position, _
      @position += written
      offset += written

    # What's the point if it doesn't make it to disk?
    fs.fsync @fd, _

    # Return the file position of the inserted record.
    position

  # Each line is terminated by a newline. In case your concerned that this
  # simple search will mistake a byte inside a multi-byte character for a
  # newline, have a look at
  # [UTF-8](http://en.wikipedia.org/wiki/UTF-8#Description). All bytes
  # participating in a multi-byte character have their leading bit set, all
  # single-byte characters have their leading bit unset.

  # Search for the newline that separates JSON records.
  _readJSON: (buffer, read) ->
    for offset in [0...read]
      if buffer[offset] is 0x0A
        return JSON.parse buffer.toString("utf8", 0, offset + 1)

  # Jump to a position in the file and read a specific object. Because objects
  # are cached in memory by a leaf tier, we're not going to get a request to
  # read an object that has been written to the current write stream. When we
  # read in a leaf tier, we'll cache any objects we encounter prior to read the
  # ordering array.
  #
  # Note how we allow we keep track of the minimum buffer size that will
  # accommodate the largest possible buffer.
  readObject: (address, _) ->
    @fd or= fs.open @filename, "a+", _
    @position or= fs.stat(@filename, _).size
    loop
      buffer = new Buffer(@length)
      read = fs.read @in, buffer, 0, buffer.length, address, _
      if json = @_readJSON(buffer, read)
        break
      if @length > @position - address
        throw new Error "cannot find end of record."
      @length += @length >>> 1
    json.pop()

  # Close the file descriptor if it is open and reset the file descriptor and
  # append position.
  close: (_) ->
    fs.close(@fd, _) if @fd
    @position = @fd = null
class exports.Strata
  # Construct the Strata from the options.
  constructor: (options) ->

    @head.next      = @head
    @head.previous  = @head
    @nextAddress    = 0
    @length         = 1024

  # Pages are identified by an integer page address. The page address is a number
  # that is incremented as new pages are created. A page file has a file name that
