Database Index - B tree, B+ tree

Why database index are used

Database index helps improve the data retrieval speed in response to certain search conditions.

Drawbacks with database index

slower write, index needs to be updated on sql updates

storage space, index may grow based on the column values

Type of Single level Database index

Fig. Sequential indexes

Ordering key field is used to physically order records on disk

Clustered index dictates the order of physical data in a table.

• can define only single cluster index on the table though it may have multiple attributes.
• clustering index has one entry for each distinct value hence non dense index
• when data is read in some sequential order or for some range it is efficient because it requires less data block reads.
• Some database define primary key as clustered index.
• If clustered index is defined on the primary key it is called Primary index.
• index entry is stored for only first record (anchor record)in each block, so its sparse index.
• Problem with it is insertion and deletion of records. Here we have to move the physical records as well as change the index entries also

Non Clustered index Data is present in random order in the table but ordering is specified by database index.

On the ordered index we can perform the binary search.

good for table whose values modify frequently.

Secondary index are dense and so one entry for each record and hence a secondary index needs more storage. There can be number of secondary index on table

 

Search Tree

Index sequential file has disadvantage that performance degrades as file grows.

the goal is to reduce the height of tree leading to less disk access

• search tree of order p has at most p children or
• (p-1) key values,ordered set of values, and p pointers, pointing to child nodes
• p1 k1 p2 k2 ....pq-1 kq-1 pq
• if any node has k children it has k-1 key values

Fig. search tree of order 4

Following condition for ordering of the keys

• each left node has key values less than parent node key value and each  right node key value greater than parent node key value
• keys in node are in ascending order

• Used for searching records on disk
• Each key value in tree is associated with a block or record pointer.
• the search tree itself can be stored on disk with each node stored in blocks
• insertion algorithms do not guarantee search tree is balanced which is important otherwise nodes at very high level would require many block access.
• deletion may leave nodes empty and may lead to more levels.

B Tree

B Tree has additional constraints that ensures balanced tree and not much space wastage on deletions

insertion and deletion are handled especially when node is full or when node becomes less than half empty on deletion

B Tree of order p is a search tree with order p with additional constraint that

• all leaves are on bottom level
• all internal nodes(except root) have at least ceil(p/2) nodes or it says each node should have at least half the maximum number of children
• root node can have as few as 2 children
• each leaf node must contain at least ceil(p/2) -1 keys

Fig. B tree of order 5

Here all internal nodes has at least ceil(5/2)= 3 children or 2 key values and each leaf node has at least 2 keys.

Any index structure other than B tree is subjected to overflow. Overflow is where any changes made to tables will not have records added into the original index structure, but rather tacked on the end.


Problem 1 Consider search field V= 9bytes block size B= 512bytes record pointer Pr=7bytes and block pointer Pb is 6bytes
How many childrens can a node have or order of tree so that each node can come in single block
Solution
let p be child pointer
a node consists of
key value + data pointer + child pointer
total size of key values ( p-1 ) * V
total size for data pointers (p-1)*Pr
total size for child pointers p*Pb
i.e (p*Pb) + (p-1)(V+Pr) <= B to fit in single block
p= 23


B+ Tree
variant of B tree datastructure
A B⁺ tree of order m is a tree where each internal node contains up to m branches (children nodes) and thus store up to m-1 search key values
order of tree measures the capacity of node or number of children nodes in internal node
B+ tree combines features of index sequential file organization with B tree
most widely used multilvel index implementation
For internal node
, where q <= p
For leaf node


where Pnext points to next leaf node
Requirements for maintaining B+ -tree
every node must contain at least ceil(n/2) pointers except for the root (which should have at least 2)
balanced: for ensuring good performance

Searching for key field value K

1) visit the root node, looking for the smallest key value greater than K. Suppose the value is Ki .
2) follow pointer Pi to another node
  - if K < K1 , then follow P1
    if K > Kmax , then follow Pmax
3) repeat step 2 until reaching a leaf node
Differences of B+-tree from B-tree

1. In B+ tree, data pointers are stored only at the leaf nodes

- more entires can be packed into internal (non-leaf) nodes of a B+ -tree than for a similar B tree meaning
B+ tree has larger fan out
- for the same block (node) size, the order p will be larger for the B+ -tree than for the B tree meaning   improved search time
- B tree eliminates redundant storage of search key values
- faster search in some cases to find desired search key values before reading a leaf node in B tree

2. Leaf and non-leaf nodes are of the same size in B+ tree, while in B tree, non-leaf nodes are larger
- complication in storage management for index structures

3. Deletion in B tree is more complicated
- in B+ tree, deleted entry always appears in a leaf
- in B tree, it can be a non-leaf node, requiring replacement by the proper value from the subtree of the node containing the deleted entry.

Problem 2 If maximum number of keys in b+ tree is 5 what is minimum number of keys in internal node and in root node.
Solution
Maximum number of childrens that a node can have(order of tree) = maximum number of keys + 1
so order of tree(b) = 5 + 1 =6
number of childrens in internal nodes(m)  is constrained by
ceil(b/2) <= m < =b
minimum number of internal nodes =  ceil(b/2) = ceil(6/2) = 3
so number of keys in that node = 3-1 = 2
 number of childrens of root node in b+tree is constrained by
2 <= m <=b
number of childrens in leaf node = no childrens of leaf node
number of keys in leaf node is constrained by
ceil(b-1/2) <= number of keys in leaf < = b-1

Problem 3
Consider a relation with 2M tuples stored in heap structure If we create a B+ tree index on this relation  with block filled to maximum capacity what would be size of tree . Assume following data
Disk page size B= 1000byte
key value(order key of relation) size V= 40bytes
disk page pointer Pb=10byte

Solution

If we were to calculate the maximum that can be stored we approach it top to bottom but if we have the entries that has to stored we approach bottom to top

Data record pointer will be stored in leaf pages since there are 2M tuples and its on order key so we will need 2M data record pointers but how many entries can a leaf page have

1) Find Number of entries a leaf page can have
leaf node stores same number of key values and record or data pointer along with a single next block pointer
so if we assume number of leaf entries to be n
n(V+ Pb) + Pb <= (size of page)  --since maximum number of entries should be allowed in a page
n = floor(size of page/(V+Pb))  -- ignoring the next block pointer for simplicity
n= 20

2) Number of leaf pages required to store 2M records = (Number of required index entries )/ (Number of index entries per leaf page)
= 2M/20 = 100000
3) Now we need to find number of entries that can come in internal nodes or branching factor m
consider number of index entries in internal node as n
each internal node will have a n-1 key values and n child pointers
(n-1)* V + n * Pb <= (B)
n =floor((B +V)/(Pb+V))
n=20

4) No we calculate Number of pages at level above leaf
there are 100000 leaf pages so we need this much index entries at level above it
so number of pages required at level above leaf = 100000 / 20 = 5000
Similarly we need to get to root that is when page is = 1
ceil(10000/20) ,ceil( 5000/20) ,ceil( 250 / 20), ceil(13 / 20) respectively for level above leaf
which is log20(100000) = 4
so we have total 5 level of pages and access to record would take 5 b tree block access  + 1 data block access = 6 disk access


References:
http://cis.stvincent.edu/carlsond/swdesign/btree/btree.html
http://www.cecs.csulb.edu/~monge/classes/share/ http://www.cs.sjsu.edu/~lee/cs157b/B_Trees_And_B__Trees.ppt
http://www.cs.virginia.edu/~son/662.pdffiles/662.physical.pdf

Serializability, Isolation Recoverability - Concurrency Control in Database

Why we want to run transactions concurrently?

Concurrent or overlapping execution of transactions are efficient

How we ensure the correctness of the concurrent transactions?

Concurrency control(Serializability) and Recovery are two criteria that ensure the correctness of concurrent transactions

Why concurrency control is needed

Lost Update : update of some data by one transaction is lost by update from another transaction
Dirty Read or temporary update problem : one transaction updates the value of common data and aborts before it can revert the changes transaction 2 reads the value of updated variable.
incorrect summary problem: transaction reads the data while another transaction is still changing the data

Why recovery is needed

In any kind of problem like hardware malfunction, software error exceptions or violating the concurrency property, deadlock recovery of transaction is needed

Transaction  states

• begin transaction marks the beginning of transaction. 
• end_transaction specifies transaction execution is complete and system check whether changes can be permanently applied.
• rollback or abort for unsuccessful end of tranaction

Fig. transaction states

• At commit point all transaction operations have been logged and new entry is done in log 'commit T' stating that all transaction operation permanently logged
• before writing commit T the complete log should be written to disk from buffers
• Rollback :  when commit T statement  is not found in log, its rollbacked

How recoverability is implemented

System log is kept on disk which logs transaction like write old value new value read.
Protocol that do not provide cascading rollback do not need to keep read entry

Schedules
Recoverable Schedule : If T2 reads a data item written by T1 commit operation of T1 should appear before commit operation of  T2.

Cascadeless Schedule: If T2 reads a data item written by T1 commit operation of T1 should appear before read operation of T2.
Strict Schedule : If a write operation of T1 precedes a conflicting operation of T2 (either read or write), then the commit event of T1 also precedes that conflicting operation of T2.

Fig. schedules recoverability

pattern for recoverable schedule would be like

Fig. simple pattern for recoverability schedules on vertical time line

What is Serializability

If executing interleaved transaction results in same outcome as serial schedule(running transaction in some sequnence) then they are considered serializable. this schedule is type of nonserial schedule.

Serializabality might be compromised in some cases but recoverability compromise would mean violating database integrity. Isolation levels decide tradeoff between correctness and concurrency


Isolation level
when the changes made by one operation becomes visible to another operation
most relaxed ACID property
From more stringent to relaxed isolation levels
Serializable as if transactions execute in complete isolation, in serial fashion. read locks released immediately but write locks released at end of transaction
Read Uncommited Dirty reads allowed that is another transaction reads the data value but then first transaction can revert so other transaction has incorrect value
Repeatable read: A phantom read occurs when range of rows is read by one transaction and another transaction inserts or delete a record in between rows returned by same query is different at two points in time for a transaction that is another transaction updates and commits in between

Read commited(Non repeatable read):prevents dirty read that is reads commited data only.
UPDATE or DELETE of any of the rows read by earlier transaction

	Dirty Read	Lost Update		Phantom Records
Read uncommitted	yes	yes		yes
Read committed	No	yes		yes
Repeatable read	No	no		yes
Serializable	No	no		no

Types of serializability

View and conflict serializability

• conflict is subset of view serializability
• Conflict is widely utilized because it is easier to determine and covers a substantial portion of the view serializable

Equivalence to serial schedule such that

In view serializable, two schedules write and read the same data values.
and In conflict seriablizable, same set of respective chronologically ordered pairs of conflicting operations.


Conflict serializable
In conflict serializabability two schedules are conflict equivalent and we can reorder the non conflicting operation to get the serial schedule
Conflicting operation
1) they are upon same data item
2)At least one of them is write
3) they are from different transactions
Non commutative that is their orders matter

Testing conflict serializability
Test is through precedence graph. The acyclic preced graph shows conflict serialiczable schedule and topological sorting of that graph gives the serializable schedules
cycle of commited transaction can be prevented by aborting an undecided transaction on each cycle in precedence graph of all transaction

view serializability is NP complete
materialized conflict if the requested conflicting operation is actually executed
//pending

Problem 1 Consider two schedules
S1 : r1(x) w1(x) r1(y) c1
S2: r2(x) r2(y) c2
1.What the number of possible schedules.
2. How many serial schedules are possible
3. Determine type of schedules(recoverable cascadeless strict) and serializability(conflict seriablizable or not) for below schedules
S1: r 1 (X); w 1 (X); r 2 (X); w 2 (X); r 1 (Y); w 1 (Y); C 2 ; C 1
S2: r 1 (X); r 2 (X); w 1 (X); r 1 (Y); w 1 (Y); C 1 ; w 2 (X); C 2
S3: r 1 (X); w 1 (X); r 2 (X); w 2 (X); r 1 (Y); w 1 (Y); C 1 ; C 2 

Solution

1.
In general, given m transactions with number of operations n1, n2, ..., nm, the number
of possible schedules is: (n1 + n2 + ... + nm)! / (n1! * n2! * ... * nm!)
here m=2 and n1= 4 and n2 = 3
so (3+4)! / (3!*4!)
7C3 or 7C4
2.Number of serial schedules is m! where m is number of transactions
so here we have 2!

3. To check type of schedule
we need to check all conflicting operations of schedule 
S1 : r2(X) comes after w1(x) , since no commit before r2(X) its not cascadeless and strict
commit of T1 should be before T2 in this case for it to be recoverable which is not so it is not even recoverable. Its non recoverable schedule
S2: there is only one conflicting operation w1(X) w2(X) and for that we have commit of T1 before w2(X) so its strict schedule and so is cascadeless also
S3: for one of the conflicting operation w1(X) r2(X) there is no commit in between so its not cascadeless and strict. To check for recoverable commit of T1 should be before that of T2 which is there

To check serializability
S1 precedence graph is
T1 ---> T2
acyclic so its conflict serializable

S2 precedence graph
T1-------->T2
^                 |

|_________|

there is cycle so its not conflict serializable

//pending problems
http://academic.udayton.edu/SaverioPerugini/courses/Winter2006/cps432/index.html

Multilevel index - Blocking factor

Why use Multilevel index?
In ordered sequential file number of block access required is log(2,b) where b is number of blocks to store the index file. Multilevel index were introduced to reduce the number of block access to access the record 

Number of block access required for multilevel index is log(bfr,b)
so number of access are less if bfr is greater than 2 for multilevel index than for ordered index file

Blocking factor

bfr  =  B/R =  (block size / record size)
blocking factor or fan out of multilevel index specifies number of records that can be accumulated in single block or records per block

Problem 1.1

Consider ordered data file with following parameters

r (number of records) = 16348
R (record size) = 32 bytes
B (block size) = 1024 bytes

index stored as key + pointer pair

key value = 10 bytes
block pointer = 6 bytes

Find the number of first level and second level blocks required for multilevel index on this

Solution:

Number of First level Blocks

Lets find Number of blocks in data file

Number of records that can be accumulated in block i.e
Blocking factor  bfr  = 1024/32 = 2^5
so, can have 32 records in a block

now how many such blocks are required for 16348 records

number of blocks required for data file =  (r/bfr)
                                                          = 16348/ 32  ~=  511

now we know we need 511 entries in the first level index

primary level of multilevel index and data file

Find 511 entries can be stored in how many blocks
i.e  how many blocks in first level of multilevel index will be required to store this much entries where each entry is of 16 bytes(key + pointer size)

R' = 16
B = 1024
bfr' = 1024/16 = 2^6

Blocking factor or fan-out for first level and its subsequent levels will be same because index entry is of same size

so number of blocks required for 512 entries would be  = r'/bfr'
                                                                                    = 511/64 = 2^3  ~= 8

secondary level index

Number of Second level Blocks

Its clear that only a single second level block would be required to store 8 entries
but lets calculate


Number of entries in second level = Number of blocks in the first level  = 8
Number of blocks in second level = (number of fist level blocks)/(bfr)
                                                    = r''/bfr'

blocking factor bfr' is same here as second level because here also we will be storing key + pointer pair
Number of records are now 8.

So, Number of blocks for second level = 8/64  ~= 1

Problem 1.2

For secondary index on unordered key data file
with same parameters

Solution:

In case of secondary index there is one index entry required for each data record in data file

Number  of First level blocks 

First level index will store index entries for all the records(16348)  in data file

Number of blocks needed for first level index = r/bfr = 16348 / 64 ~= 256
(bfr = 1024/(10+6) )

Number of second level blocks


Number of entries in second level = Number of blocks in first level = 256
bfr = 64 is same and r = 256
so Number of second level blocks = 256/64 = 4