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
Les avantages d'acheter des résumés chez Stuvia:
Qualité garantie par les avis des clients
Les clients de Stuvia ont évalués plus de 700 000 résumés. C'est comme ça que vous savez que vous achetez les meilleurs documents.
L’achat facile et rapide
Vous pouvez payer rapidement avec iDeal, carte de crédit ou Stuvia-crédit pour les résumés. Il n'y a pas d'adhésion nécessaire.
Focus sur l’essentiel
Vos camarades écrivent eux-mêmes les notes d’étude, c’est pourquoi les documents sont toujours fiables et à jour. Cela garantit que vous arrivez rapidement au coeur du matériel.
Foire aux questions
Qu'est-ce que j'obtiens en achetant ce document ?
Vous obtenez un PDF, disponible immédiatement après votre achat. Le document acheté est accessible à tout moment, n'importe où et indéfiniment via votre profil.
Garantie de remboursement : comment ça marche ?
Notre garantie de satisfaction garantit que vous trouverez toujours un document d'étude qui vous convient. Vous remplissez un formulaire et notre équipe du service client s'occupe du reste.
Auprès de qui est-ce que j'achète ce résumé ?
Stuvia est une place de marché. Alors, vous n'achetez donc pas ce document chez nous, mais auprès du vendeur chloewalt. Stuvia facilite les paiements au vendeur.
Est-ce que j'aurai un abonnement?
Non, vous n'achetez ce résumé que pour $10.82. Vous n'êtes lié à rien après votre achat.
