24-07-2012, 11:19 AM
Multilevel Indexing and B+ Trees
btrees.ppt (Size: 416 KB / Downloads: 228)
Indexed Sequential Files
Provide a choice between two alternative views of a file:
Indexed: the file can be seen as a set of records that is indexed by key; or
Sequential: the file can be accessed sequentially (physically contiguous records), returning records in order by key.
Example of applications
Student record system in a university:
Indexed view: access to individual records
Sequential view: batch processing when posting grades
Credit card system:
Indexed view: interactive check of accounts
Sequential view: batch processing of payments
Maintaining a Sequence Set
Sorting and re-organizing after insertions and deletions is out of question. We organize the sequence set in the following way:
Records are grouped in blocks.
Blocks should be at least half full.
Link fields are used to point to the preceding block and the following block (similar to doubly linked lists)
Changes (insertion/deletion) are localized into blocks by performing:
Block splitting when insertion causes overflow
Block merging or redistribution when deletion causes underflow.
Formal definition of B+ Tree Properties
Properties of a B+ Tree of order v :
All internal nodes (except root) has at least v keys and at most 2v keys .
The root has at least 2 children unless it’s a leaf..
All leaves are on the same level.
An internal node with k keys has k+1 children