Crisp Reading Notes on Latest Technology Trends and Basics

In this short note, we elaborate on a short and crisp algorithm to lock the nodes of a B-Tree and of the Indexes, while executing the standard operations of “Select” and “Insert”

Tree-based Algorithm

Search Operation

The following enhanced algorithm will work well for the Select algorithm, while traversing the B-tree

lock root of B-tree

while ( not at leaf ) {

lock child;

unlock parent;

}

The algorithm works because

  • During a “Select”, a node is never revisited
  • Also, all Insert/Delete operations must follow the same path during their traversal.

Insert/Delete Operation

The following is a simple algorithm for Insert/Delete

  • For  inserts, changes made to the leaf of the tree cause splits on the parent and ancestors
    • Until a non-full node is reached ( This is called a safe-child )
  • For deletes, changes made to the leaf of the tree cause merges on the parent and ancestors
    • Until a non half-empty node is reached ( This is called a safe-child )
lock root of B-tree

while ( not at leaf ) {

lock child;

if ( child is safe ) {

// The split will stop at the child. So

release all nodes held, except for the child

}

}

Optimized Insert/Delete Algorithm

The following algorithm performs very well in practice

lock leaf

if (leaf is not safe ) {

unlock leaf;

restart with normal insert/delete algorithm

}

Index Locking

Predicate Locks

When a query executes a Predicate, other transactions may add fresh data, and we may see only a portion of their effects. This becomes non-serializable.

  • If there is an Index for the predicate,
    • Predicate locks are achieved by locking the Index on specific pages for entries containing the predicate value
    • Or by locking the pages where the Predicate value would have been placed.
  • If there is no Index for the predicate,
    • The entire table needs to be locked.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Tag Cloud

%d bloggers like this: