IFSC 7320 Midterm Review Topics Xiaowei Xu

1

Midterm will cover material from: • Lectures 1-­‐7 • Database Systems (M. Kifer, A. Bernstein and P. M. Lewis)

– Chapter 9 secAons 9.1 through 9.6.1 – Chapter 9 secAon 9.8 – Chapter 12 secAon 12.2.1

2

Midterm exam

• Day and Ame:

– Thursday, October 8, 2015 – 6 PM to 8 PM

• No books, homework assignments, lecture slides or any other documents are allowed for this exam.

– has to complete individually by each student

3

Topics covered on midterm: •
•
•
•
•

Physical disk organizaAon RAID levels Heap files Sorted files Indices – Integrated versus unintegrated – Clustered versus unclustered – Sparse versus dense – MulAple a[ribute search keys

4

Topics covered on midterm:

• MulAlevel indexing – ISAM – B+ Trees • Searching B+ Trees • InserAng into B+ Trees

•
•
•
•

Hash indices Choosing indices for queries Designing indices (SecAon 12.2.1) Index covering 5

Physical Disk Structure

6

Disk Latency • The distance between disk sectors in increasing order: 1.
2.
3.
4.

Two adjacent sectors on the same track Two sectors on same track Two sectors on the same cylinder Two sectors on different cylinders

7

RAID Systems • RAID (Redundant Array of Independent Disks) is an array of disks configured to behave like a single disk with – Higher throughput • MulAple requests to different disks can be handled independently • If a single request accesses data that is stored separately on different disks, that data can be transferred in parallel

– Increased reliability • Data is stored redundantly • If one disk should fail, the system can sAll operate 8

Striping • Data that is to be stored on mulAple disks is said to be striped – Data is divided into chunks • Chunks might be bytes, disk blocks etc.

– If a file is to be stored on three disks • First chunk is stored on first disk • Second chunk is stored on second disk • Third chunk is stored on third disk • Fourth chunk is stored on first disk • And so on 9

The Striping of a File Across Three Disks F1

F2

F3

F4

10

Levels of RAID System • Level 0: Striping but no redundancy – A striped array of n disks – The failure of a single disk ruins everything

11

RAID Levels (con’t) – Level 1: Mirrored Disks (no striping) • An array of n mirrored disks – All data stored on two disks

• Increases reliability – If one disk fails, the system can conAnue

• Increases speed of reads – Both of the mirrored disks can be read concurrently

• Decreases speed of writes – Each write must be made to two disks

• Requires twice the number of disks 12

RAID Levels (con’t) • Level 3: Data is striped over n disks and an (n
+1)th
disk is used to stores the exclusive or (XOR) of the corresponding bytes on the other n disks – The (n+1)th disk is called the parity disk – Chunks are bytes

13

Level 3 (con’t) • Redundancy increases reliability – Secng a bit on the parity disk to be the XOR of the bits on the other disks makes the corresponding bit on each disk the XOR of the bits on all the other disks, including the parity disk – 1 0 1 0 1

1 (parity disk) – If any disk fails, its informaAon can be reconstructed as the XOR of the informaAon on all the other disks 14

Level 3 (con’t) • Whenever a write is made to any disk, a write must by made to the parity disk – New_Parity_Bit = Old_Parity_Bit XOR (Old_Data_Bit XOR New_Data_Bit)

• Thus each write requires 4 disk accesses • The parity disk can be a bo[leneck since all writes involve a read and a write to the parity disk 15

RAID Levels (con’t) • Level 5: Data is striped and parity informaAon is stored as in level 3, but – The chunks are disk blocks – The parity informaAon is itself striped and is stored in turn on each disk • Eliminates the bo[leneck of the parity disk

– Level most ogen recommended for transacAon processing applicaAons

16

RAID Levels (con’t) • Level 10: A combinaAon of levels 0 and 1 (not an official level) – A striped array of n disks (as in level 0) – Each of these disks is mirrored (as in level 1) • Achieves best performance of all levels • Requires twice as many disks

17

MulAple A[ribute Search Key • CREATE INDEX Inx ON Tbl (A+1, A+2) • Search key is a sequence of a[ributes; index entries are lexically ordered • Supports finer granularity equality search:

– “Find row with value (A1, A2) ”

• Supports range search (tree index only): – “Find rows with values between (A1, A2) and (A1ʹ′, A2ʹ′) ”

• Supports parAal key searches (tree index only): – Find rows with values of A+1 between A1 and A1ʹ′ – But not “Find rows with values of A+2 between A2 and A2ʹ′ ”

18

Pages accessed when selecEng from a B+ tree 1

2

3 7

8

4 10

11

5 6

SELECT *
FROM Student S
WHERE S.name = “karen”

9

12

Pages accessed: 1, 3, 8

19

Pages accessed when selecEng from a B+ tree 1

2

3 7

8

4 10

11

5 6

9

SELECT *
FROM Student S
WHERE S.name > john AND S.name < smith

12

Pages accessed: 1, 2, 7, 8, 9, 10, 11

20

Handling InserAons -­‐ Example - Insert “vince”

21

Handling InserAons -­‐ Example - Insert “vince”

22

Handling InserAons (cont’d) - Insert “vera”

vince

23

Handling InserAons (cont’d) – Insert “vera”: Since there is no room in leaf page:
1. Create new leaf page, C
2. Split index entries between B and C (but maintain sorted order)
3. Add separator entry at parent level

24

Handling InserAons (cont’d) Insert “rob”.

25

Handling InserAons (con’t) – Insert “rob”. Since there is no room in leaf page A:
1. Split A into A1 and A2 and divide index entries between the two (but maintain sorted order)
2. Split D into D1 and D2 to make room for additional pointer 3. Three separators are needed: “sol”, “tom” and “vince”

26

Handling InserAons (cont’d) – When splitting a separator page, push a separator up
– Repeat process at next level
– Height of tree increases by one

27