B+Trees sorted by size and location (a-la XFS) provides:
– ability to allocate large/small objects efficiently (size)
– ability to allocate blocks near existing objects (e.g. for object expansion) by using the location B+Tree

B+Trees are good, therefor use them.

Split up into allocation groups (a-la XFS and BFS). Allows more parallel operation as different threads can work on different allocation groups (during updating).

Idea for fine grained B+Tree locking:
– each node gets an ID (which should be pretty unique… but not essential to correct operation).
– when process needs to update node, places a lock on it’s ID
– when a process accesses a node, before reading, it checks to see if a lock has been placed on that ID. IF so, we spin, waiting for the lock to be released
– when a process has finished updating a node, it releases the lock on it’s ID.
– the process waiting to read it will stop spinning and be able to read the new copy.

IF IDs overlap, there is no problem, we’ll just be spinning when a different node is being updated.

However, if we are updating a tree of nodes, then some careful locking wil have to be employed, from the BOTTOM UP! that is, update from the bottom up, locking each individual one as we go as if we only lock the root of the tree being updated, another process could have already passed it and screw us up royally.