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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller chloewalt. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $11.06. You're not tied to anything after your purchase.
