1 of 54

2 of 54

3 of 54

Do we need per-record metadata?

4 of 54

Do we need metadata?

No. Each field has the same length for every record.

5 of 54

6 of 54

7 of 54

8 of 54

9 of 54

10 of 54

11 of 54

				‘0123’	‘PHO 206’	199

12 of 54

				‘0123’	‘PHO 206’	199

0

2

4

6

8

12

19

23

13 of 54

8				‘0123’	‘PHO 206’	199

0

2

4

6

8

12

19

23

14 of 54

8	12			‘0123’	‘PHO 206’	199

0

2

4

6

8

12

19

23

15 of 54

8	12	19		‘0123’	‘PHO 206’	199

0

2

4

6

8

12

19

23

16 of 54

8	12	19	23	‘0123’	‘PHO 206’	199

0

2

4

6

8

12

19

23

Length of bytes? 23

17 of 54

18 of 54

8	-1	12	16	‘0123’	199

a.

b.

c.

d.

8	-1	12	16	‘0123’	NULL	199

8	12	-1	16	‘0123’	NULL	199

8	12	-1	16	‘0123’	199

19 of 54

8	-1	12	16	‘0123’	199

a.

b.

c.

d.

8	-1	12	16	‘0123’	NULL	199

8	12	-1	16	‘0123’	NULL	199

8	12	-1	16	‘0123’	199

20 of 54

				‘0123’	199

21 of 54

				‘0123’	199

0

2

4

6

8

12

16

22 of 54

8				‘0123’	199

0

2

4

6

8

12

16

23 of 54

8	-1			‘0123’	199

0

2

4

6

8

12

16

24 of 54

8	-1	12		‘0123’	199

0

2

4

6

8

12

16

25 of 54

8	-1	12	16	‘0123’	199

0

2

4

6

8

12

16

26 of 54

15 30 45

7 12

17 22 27

32 38 43

…

55

…

27 of 54

15 30 45

7 12

17 19 22 27

32 38 43

…

55

…

28 of 54

15 30 45

7 12

17 19 22 25 27

32 38 43

…

55

…

29 of 54

15 22 30 45

7 12

17 19

32 38 43

…

55

…

25 27

30 of 54

15 22 30 45

7 12

17 19

32 38 41 43

…

55

…

25 27

31 of 54

15 22 30 45

7 12

17 19

32 38 40 41 43

…

55

…

25 27

32 of 54

15 22 30 40 45

7 12

17 19

32 38

…

55

…

25 27

41 43

33 of 54

15 22

7 12

17 19

32 38

…

30 55

…

25 27

41 43

40 45

34 of 54

In a B+tree, the full key-value pairs are all stored in leaf nodes. The interior nodes only contain keys.

When a node is split, the middle key is sent up and inserted in the parent, but the corresponding key-

value pair remains at the leaf level, in the new node that is created as part of the split.

35 of 54

15 30 45

7 12

17 22 27

30 38 43

…

55

…

36 of 54

15 30 45

7 12

17 19 22 27

30 38 43

…

55

…

37 of 54

15 30 45

7 12

17 19 22 25 27

30 38 43

…

55

…

38 of 54

15 22 30 45

7 12

17 19

30 38 43

…

55

…

22 25 27

39 of 54

15 22 30 45

7 12

17 19

30 38 41 43

…

55

…

22 25 27

40 of 54

15 22 30 45

7 12

17 19

30 38 40 41 43

…

55

…

22 25 27

41 of 54

15 22 30 40 45

7 12

17 19

30 38

…

55

…

22 25 27

40 41 43

42 of 54

15 22

7 12

17 19

30 38

…

30 55

…

22 25 27

40 41 43

40 45

43 of 54

44 of 54

45 of 54

f = 4, n = 2

Add bucket when

f > 2n

f > 4

*Add bucket on next insert

46 of 54

Insert 436

47 of 54

Insert 436

436 % 10 = 6 = 0110

48 of 54

Insert 436

436 % 10 = 6 = 0110

f > 2n, add bucket

49 of 54

Insert 436

436 % 10 = 6 = 0110

f > 2n, add bucket

50 of 54

Insert 436

436 % 10 = 6 = 0110

f > 2n, add bucket

rehash!

51 of 54

52 of 54

00 [1000]

01 [713]

10 [972, 12, 436]

insert 113

53 of 54

00 [1000]

01 [713]

10 [972, 12, 436]

insert 113

113 % 10 = 3

3 = 0011

54 of 54

insert 116

Split

rehash