Formula Sheets: File Organization & Indexing | Database Management System (DBMS) - Computer Science Engineering (CSE) PDF Download

 Page 1


File Organization and Indexing
File Organization
Sequen tial File Organization
• Records stored in sequen tial order (e.g., sorted b y k ey).
• A ccess Time: O(n) for searc h, O(1) for sequen tial read.
• Space Complexit y: O(n) , where n is n um b er of re cords.
Indexed Sequen tial File Organization
• Re cords stored sequen tially with index for faster access.
• Searc h Time: O(logk +m) , where k is index size, m is blo c k size.
• Space C omplexit y: O(n+k) , where k is index storage.
Direct A ccess File Organization
• Records a ccessed via hash function or k ey mapping.
• A ccess T ime: O(1) a v erage, O(n) w orst case (collisions).
• Space Com plexit y: O(n) .
Cluster Fi le Organization
• Related rec ords group ed in clusters for faster retriev al.
• A ccess Tim e: O(c+m) , where c is cluster access time, m is records in cluster.
• Space Complexit y: O(n) .
Indexing
Primary Inde x
• Index on primary k ey , stored with data file.
• Searc h Time: O(logk) , where k is index en tries.
• Space Complexit y: O(k) , t ypically k« n .
Secondary Index
• Index on non-k ey attributes, s eparate from data file.
• Searc h Time: O(logk +m) , where m is n um b er of matc hing records.
• Space Complexit y: O(k) .
Clustered vs Non-Cluste red Index
• Clustered: Data ph ysically sorted b y index k ey; 1 p er table.
• Non-Clustered: Separate index, d ata not sorted; m ultiple allo w ed.
B-T ree
• Balanced tree, degree t : Eac h no de (except r o ot) has [t-1,2t-1] k eys.
• Heigh t: h= log
t
?(n+1)/2? , where n is n um b er of k eys.
• Searc h Time: O(log
t
n) .
• Insert/Delete Time: O(tlog
t
n) .
• Space Complexit y: O(n) .
B+ T ree
• Leaf no des store all k eys and data p oin ters, in ternal no des store k eys only .
1
Page 2


File Organization and Indexing
File Organization
Sequen tial File Organization
• Records stored in sequen tial order (e.g., sorted b y k ey).
• A ccess Time: O(n) for searc h, O(1) for sequen tial read.
• Space Complexit y: O(n) , where n is n um b er of re cords.
Indexed Sequen tial File Organization
• Re cords stored sequen tially with index for faster access.
• Searc h Time: O(logk +m) , where k is index size, m is blo c k size.
• Space C omplexit y: O(n+k) , where k is index storage.
Direct A ccess File Organization
• Records a ccessed via hash function or k ey mapping.
• A ccess T ime: O(1) a v erage, O(n) w orst case (collisions).
• Space Com plexit y: O(n) .
Cluster Fi le Organization
• Related rec ords group ed in clusters for faster retriev al.
• A ccess Tim e: O(c+m) , where c is cluster access time, m is records in cluster.
• Space Complexit y: O(n) .
Indexing
Primary Inde x
• Index on primary k ey , stored with data file.
• Searc h Time: O(logk) , where k is index en tries.
• Space Complexit y: O(k) , t ypically k« n .
Secondary Index
• Index on non-k ey attributes, s eparate from data file.
• Searc h Time: O(logk +m) , where m is n um b er of matc hing records.
• Space Complexit y: O(k) .
Clustered vs Non-Cluste red Index
• Clustered: Data ph ysically sorted b y index k ey; 1 p er table.
• Non-Clustered: Separate index, d ata not sorted; m ultiple allo w ed.
B-T ree
• Balanced tree, degree t : Eac h no de (except r o ot) has [t-1,2t-1] k eys.
• Heigh t: h= log
t
?(n+1)/2? , where n is n um b er of k eys.
• Searc h Time: O(log
t
n) .
• Insert/Delete Time: O(tlog
t
n) .
• Space Complexit y: O(n) .
B+ T ree
• Leaf no des store all k eys and data p oin ters, in ternal no des store k eys only .
1
• Heigh t: h= log
?t/2?
?n/t? .
• Se arc h Time: O(log
t
n) .
• Ins ert/Delete Time: O(log
t
n) .
• Space Complexit y: O(n) .
• Range Q uery: O(log
t
n+k) , where k is n um b er of matc hing records.
Extendible Hashing
• Directory Siz e: 2
d
, where d is global depth.
• Buc k et Spli t: When buc k et o v erflo ws, lo cal depth l= d .
• Searc h/Insert/Delete Time: O(1) a v erage, O(logn) w orst case (directory expansion).
• Space C omplexit y: O(n+2
d
) .
• Directory Doubling: W hen l > d , d = d+1 , size doubles.
RAID
RAID Lev els
• RAID 0: Striping, n o redundancy; Read/W rite: O(1) , F ault T olerance: None.
• RAID 1: Mirroring; R ead: O(1) , W rite: O(n) , F ault T olerance: 1 disk.
• RAID 5: Striping w ith parit y; Read/W rite: O(n) , F ault T olerance: 1 disk.
2