These notes cover all the following concepts, with diagrams, explanations and examples: Disk structure and data, indexing, B-trees, B+ trees, priority queues, binary heaps, heapify, graphs: Adjacency matrix, breadth first search, dijkstra, negative weight graphs and directed acyclic graphs, bellman...
1. Disk Structure: Made up of tracks and sections. A block consists of a track number and
sector number. Below would be a block that is sector 1, track 2.
2
1
When we want to access data, it must be loaded from disk to main memory. Only then it
can be accessed. The data inside the main memory that is directly used by the program is a
data structure. The data is organized by the data structure in the main memory. The storage
on disk uses a database management system (DBMS).
2. How is data organized in the disk structure?
SID Name dept Let’s say there are 100 rows that take up 512B
1 John … Student:
2 Tom SID(10), Name(50), dept(10), section(8), add(50) =128
3 Sahil Bytes per student. Thus, can fit 4 records per block.
4 Jerry First 4 go into first block, next 4 into second block.
5 Smitt
6 Thus, 25 blocks are required for storing this table on
7 disk.
3. Index:
Will store the key (Student ID) and a pointer. Let’s say the SID and pointer is 16B. The blockis
512B. 512/ 16 = 32 Records per block. 100 records / 32 records/block= 3.2 blocks for storing
the index (basically 4 blocks). Then we search, we access index. Uses 4+1 (5 blocks) instead
of 25. This is the benefit of indexes.
SID Pointer SID Name dept
1 1 John …
2 2 Tom
3 3 Sahil
4 4 Jerry
5 5 Smitt
6 6
7 7
, 4. Multi-Level indexes:
What if there are thousands of records?
Multi-Level:
1 SID Pointer SID Name dept
33 1 1 John …
2 2 Tom
3 3 Sahil
4 4 Jerry
16B per block
5 5 Smitt
Thus, can store it all
6 6
In 2 blocks
7 7
32 entries
Points to new block
Reducing the number of block access by using indexes and multi-level indexes.
We want to use self-managing high level indexes, multi-level indexing.
Multilevel indexing
rotated looks like a tree.
The right is multilevel
indexing, left is rotated
that represents a tree
structure.
5. M-way Search Tree:
- Each node can have at most m children and a maximum (m-1) keys.
- Eg: 4-way tree has maximum 4 children and 3 keys.
K1 K2 K3
Child pointer, key, record
Pointer.
Cp1 Rp Cp2 Rp Cp3 Rp
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper chloewalt. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €10,18. Je zit daarna nergens aan vast.
