{CSC2001F
[Chloe Walt] [Year 2, Semester 1, 2021]
Data Structures 2
Chloe Walt
WLTCHL002 |
,DATA STRUCTURES 2:
B-TREES AND B+ TREES:
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
[Chloe Walt] [Year 2, Semester 1, 2021]
Data Structures 2
Chloe Walt
WLTCHL002 |
,DATA STRUCTURES 2:
B-TREES AND B+ TREES:
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
