             self.right = right
           delete ordered[page.right]
           
-class Reader
+class Iterator
   constructor: (@_io, @_page, @_index, @_key, @_found, @_exclusive) ->
     @_exclusive or= false
     @_offset = 0

    index = @find page, @key, 0, _
    index = ~index if not (found = index >= 0)

    cursor = if exclusive then Writer else Reader
    cursor = new cursor(@io, page, index, @key, found)

    @io.unlock page for page in @shared


# ## Descent
#
# A *decent* is a b-tree operation.  We use the term
# descent to describe both top down and left right traversal of our b-tree.
#
# When we want to retreive records from the b-tree, or alter the b-tree in any
# way, first we descend the tree. When we navigate to leaf pages of a search
# b-tree to obtain records, we *search* the b-tree. When we change the b-tree in
# any way, adding or deleting records, splitting or merging pages, we *alter*
# the b-tree.
#
# A descent is analogous to a thread, because one can make progress while
# another descent is waiting on I/O.
#
# A decent an make progress while other decents make progress, even though
# Node.js only has a single thread of execution. When we descend the tree, we
# may have to wait for evented I/O to read or write a page. While we wait, we
# can make progress on another descent in the main thread of execution.
#
# Because descents can make progress in parallel, we need to synchronize access
# to b-tree pages, as we would with a multi-threaded b-tree implementation. When
# we descend the b-tree we need to make sure that we do not alter pages that
# another waiting descent needs to complete its descent when it awakes, nor read
# pages that a waiting descent had begun to alter before it had to wait.
#
# These are race conditions. We use the shared read/exclusive write locks
# described in the `IO` class above to guard against these race conditions.
#
# #### Locking on Descent
#
# Becase a search descent does not alter the structure of the b-tree, Multiple
# search descents can be performed concurrently, without interfering with each
# other.
#
# Descents that alter the b-tree exclusive access, but only to the pages they
# alter. A search descent can still make progres in the presence of an
# alteration decent, so long as the search does not visit the pages being
# altered.
#
# A search descent obtains shared locks on the pages that it visits.  An
# alteration descent obtains exclusive locks on the pages that it needs to
# alter. The alteration descent will obtain shared locks on the pages that
# visits in search the pages that it wants to alter.
#
# #### Locking Hand Over Hand
#
# To allow progress in parallel, we lock only the pages we need to descend the
# tree, for only as long as we takes to determine which page to visit next.
# Metaphically, we descend the tree locking hand-over-hand.
#
# We start from the root page. We lock the root page. We perform a binary search
# that compares our search key against the keys in the root page. We determine
# the correct child page to visit to continue our search. We lock the child
# page. We then release the lock on the parent page.
# 
# We repeat the process of locking a page, searching it, locking a child, and
# then releasing the lock on the child's parent.
#
# We hold the lock on the parent page while we aquire the lock on the child page
# because we don't want another descent to alter the parent page, invaliding the
# direction of our descent.
#
# #### Lateral Traversal
#
# Both branch pages and leaf pages are singly linked to their right sibling. If
# you hold a lock on a page, you are allowed to obtain a lock on its right
# sibling. This left right ordering allows us to traverse a level of the b-tree,
# which simplifies the implemtation of record cursors and page merges.
#
# When we move from a page to its right sibling, we hold the lock on the left
# page until we've obtained the lock on the right sibling. The prevents another
# descent from relinking linking our page and invalidating our traversal.
#
# #### Deadlock Prevention and Traversal Direction
#
# To prevent deadlock, we always move form a parent node to a child node, or
# form a left sibling to a right sibling.
# so that we do not create a condition
# where on descent 
#
# Othewise we would deadlock when a descent that has an exclusive lock on a
# parent attempted to obtain a lock on child, while another descent has either
# sort of lock on the child attempted to obtain a lock on the parent. By only
# obtaining locks top down, we avoid this deadlock condition because all of the
# descents obtain locks in the same order.
#
# When traversing the tree laterally, we always travel from a page to the right
# sibling of that page. Two descents traversing a level in both directions would
# deadlock when they encountered each other, if one of the descents was locking
# exclusively.
#
# To prevent a deadlock when a left right traversal coincides with the top down
# traversal, we insist that when a parent obtains a lock on more than one child,
# it locks the children in left to right order. That is, we must remember the
# left right ordering regardless of whether we're navigating using a page's link
# to it's right sibling, or whether we're referencing a branch page's children
# pages.
#
# #### Insertion and Deletion Verus Balance
#
# We do not attempt to balance the tree with every insertion or deletion. The
# client may obtain a cursor to the leaf pages, iterate through them deleting
# records along the way. Balacing 
#
# #### Staccato Blanace Operations
#
# The b-tree balance operations cascade by nature. If you insert a value into a
# leaf node, such that the leaf node is beyond capacity, you split the leaf
# node, adding a new child to the parent node. If the parent node is now beyond
# capacity, you split the parent node, adding a new child to its parent node.
# When every node on the path to the leaf node is at capacity, a split of the
# leaf node will split every node all they way up to the root.
#
# Merges too move from leaves to root, so that a merge at one level of the
# b-tree potentially triggers a merge of the parent with one of its siblings.
#
# However, we've established rules for lock acquisition that require that locks
# are obtained from the top down, and never from the bottom up. This is why we
# do not perform balance operations as a part of a single pass. We instead
# descend the tree once to insert or delete records form the leaf pages. We then
# descend the tree once for each split or merge of a page.
#
# Much b-tree literature makes mention of a potential efficency where you split
# full pages on the way back up from an insert. You can determine which pages
# would split if the leaf split as you descend the b-tree, since you'll visit
# every page that would participate in a split.
#
# That efficency applies only for split, and not for merge, because you have to
# inspect the left and right siblings of a page to determine if it is time to
# merge. If the left sibling page of a page, is not also child of that page's
# parent page, then the left sibling page is in a different sub-tree. It can not
# be reached by the path that was used to find the leaf page where the delete
# occured.
#
# The single pass insert on the way down and split on the way up violates the
# rules we laid out to prevent deadlock. To abide by our rules, we'd have to
# lock exclusively on the way down, then hold the locks on the pages above the
# leaf page that were full and could possibly split. This would reduce the
# liveliness of our implementation.
#
# There are compromises, but rather than create a complicated locking apparatus,
# with upgrades, we're going to simplify our algorithm greatly, by descending
# the tree once for each split or merge. 
#
# When we travel to the unbalanced page, we acquire shared locks in the hand
# over hand fashion used for search. We acquire exclusive locks only on those
# pages that participate in the balance operation. That is two pages in the case
# of the split. In the case of a merge that is three pages. During a balance
# operation are locking exclusively, at most, three pages at a time.
#
# If out balance operation casades so that it requires a balance at every level,
# we'll descend the tree once for every level. However, the path we follow is
# almost certain to be in memory, since we're revisting the same path.
#
# Also, a balance operation will involve an increasing number of levels with
# decreasing frequency. A split will most often require that only the leaf page
# is split. The penultimate pages will be involved in a balance operation at
# least an order of mangitude less frequently. The pages above the penultimate
# branch pages will be involved in a balance operation yet another order of
# mangniutde less frequently.
#
# Conserving descents during balance operations is a false economy. It
# complicates lock acquisition. It reduces the liveliness of the b-tree.
#
# The multiple descents will allow searches of the b-tree to make progress
# between balance operations.
#
# ##### Descent as Unit of Work
#
# We can see that a descent of the tree is analogous to a thread in
# multi-threaded operation. A decent is an actor on the tree, performing a
# single balance operation, searching 
#
# ##### Delayed Balance
#
# We've determined that we do not want to perform a split or merge of the leaf
# level the moment we've detected the need for one. If we fill a leaf page, we
# descend the tree again to split the leaf page.
#
# Because the b-tree is a concurrent structure, the leaf split descent may
# discover that another descent has removed a record, and a leaf split is no
# longer necessary. There may be, in fact, a descent on the way to the left
# sibling of the page, to check for the potential for a merge.
#
# The concurrent operation means that we have to deal with situation where we've
# undertaken a descent to balance the b-tree, but another series of descents
# has rendered that plan invalid.
#
# As long as we're dealing with that problem, we may as well decouple insertion
# and deletion form split and merge entirely, and see if we can't gain more
# liveliness, and a simpiler implementation, by separating these concerns.
#
# We can provide an interface where the application developer can insert or
# delete any number of records, then order a balance of the tree that takes all
# the changes into account. This can avoid degenerate cases of sort where a leaf
# page at the split threshold and the application in turn inserts and deletes a
# single record from it.
#
# We can provide the application developer with a cursor. The cursor can delete
# a range of values, or insert a range of values, without having to descend the
# tree for each inserted value. The developer can insert or delete records as
# fast as the operating system can append a string to a file. We'll balance this
# mess for her later.
#
# It is still cheap to check for balance for single inserts or deletes, as if we
# were checking as part of a single pass.
#
# ##### Balance Thread
#
# We perform balance operations one a time. We do not begin a new balance
# operation until the previous one completes. In essence, we perform balancing
# in a separate thread of execution.
#
# Of course, a Node.js application really only has one thread of execution. In
# our b-tree, however, multiple descents can make progress at the time, or
# rather, the progress made by one decent, while another descent waits on I/O.
#
# We ensure that only one descent at a time is making progress toward the
# balance of the tree. This simpilies or balance implementation, because the
# structure of the tree, its depth and number of pages, will only be changed one
# one series of descents. A balance descent can assume that the tree retain its
# structure while the balance descent waits on I/O.
#
# ##### Balancer
#
# We will call the code that co-ordinates the series of splits and merges to
# balance the tree, the *balancer*.
#
# ### Merging
#
