1 of 100

Discussion 3

B+ Trees

2 of 100

Announcements

Vitamin 3 (B+ trees) is due Mon 9/21 at 11:59PM.

Project 2 (B+ trees) is due Thurs 9/24 at 11:59PM.

Midterm 1 Alterations Form released, due Sun 9/20 at 11:59PM.

3 of 100

Indices (B+ Trees)

4 of 100

Indices

Data structure to allow for fast lookup on some search key

Lookup could be equality, 1D range, 2D range, etc.
Search key is a subset of columns, may not be unique

Index may store pointers to heap file (i.e. <key, recordId>) or entire records

5 of 100

B+ trees

A type of index (there are others!)

We’ll mostly be looking at B+ trees in this class.

Leaf nodes (nodes at the bottom of the tree) contain data entries (e.g. <key, recordId>)
Inner nodes (nodes not at the bottom) are solely for lookup

No data entries are stored in these!

6 of 100

B+ trees

We use d to denote the order of the tree
Each node (both inner and leaf) contains up to 2d values
Height = # of pointers from root to a leaf node

B+ tree w/ 1 node is height 0, root node is a leaf node
For B+ trees w/ height > 0, root node is an inner node

7 of 100

B+ trees

Inner nodes contain up to 2d values, and have a maximum fanout of 2d+1

Key invariant: for each key in an inner node, we have (1) a reference to another node for search key values <x, and (2) a reference to another node for search key values ≥ x

8 of 100

B+ trees

To keep the fanout high (for performance guarantees), we have an occupancy invariant: every inner node (except the root) must be at least half full (at least d values)

17

13

5

30

24

2*

3*

5*

7*

8*

14*

16*

19*

20*

22*

24*

27*

29*

33*

34*

38*

39*

Root Node

Page 2

Page 4

Page 3

Page 1

Page 5

Page 6

Page 7

Page 8

Page 9

9 of 100

B+ trees

We may also add sibling pointers between leaf nodes

Helps for scanning in sorted order

17

13

5

30

24

2*

3*

5*

7*

8*

14*

16*

19*

20*

22*

24*

27*

29*

33*

34*

38*

39*

Root Node

Page 2

Page 4

Page 3

Page 1

Page 5

Page 6

Page 7

Page 8

Page 9

10 of 100

Searching B+ Trees

11 of 100

B+ trees: Search for 27

Find key = 27

Find split on each node
Follow pointer to next node

17

13

5

30

24

2*

3*

5*

7*

8*

14*

16*

19*

20*

22*

24*

27*

29*

33*

34*

38*

39*

Root Node

12 of 100

B+ trees: Search for 27

Find key = 27

Find split on each node
Follow pointer to next node

17

13

5

30

24

2*

3*

5*

7*

8*

14*

16*

19*

20*

22*

24*

27*

29*

33*

34*

38*

39*

Root Node

13 of 100

B+ trees: Search for 27

Find key = 27

Find split on each node
Follow pointer to next node

17

13

5

30

24

2*

3*

5*

7*

8*

14*

16*

19*

20*

22*

24*

27*

29*

33*

34*

38*

39*

Root Node

14 of 100

B+ trees: Search for 27

Find key = 27

Find split on each node
Follow pointer to next node

17

13

5

30

24

2*

3*

5*

7*

8*

14*

16*

19*

20*

22*

24*

27*

29*

33*

34*

38*

39*

Root Node

27*

15 of 100

Inserting into B+ Trees

16 of 100

B+ trees: insert 25

Find the correct leaf node

17

24

13

30

Root Node

2*

3*

5*

7*

14*

16*

19*

20*

22*

24*

27*

29*

33*

34*

38*

39*

17 of 100

B+ trees: insert 25

Find the correct leaf node

17

24

13

30

Root Node

2*

3*

5*

7*

14*

16*

19*

20*

22*

24*

27*

29*

33*

34*

38*

39*

18 of 100

B+ trees: insert 25

Find the correct leaf node
If there is room in leaf, just add the entry

17

24

13

30

Root Node

2*

3*

5*

7*

14*

16*

19*

20*

22*

24*

27*

29*

33*

34*

38*

39*

19 of 100

B+ trees: insert 25

Find the correct leaf node
If there is room in leaf, just add the entry

17

24

13

30

Root Node

2*

3*

5*

7*

14*

16*

19*

20*

22*

24*

27*

29*

33*

34*

38*

39*

20 of 100

B+ trees: insert 25

Find the correct leaf node
If there is room in leaf, just add the entry

21 of 100

B+ trees: insert 25

Find the correct leaf node
If there is room in leaf, just add the entry

And keep the leaf node sorted

17

24

13

30

Root Node

2*

3*

5*

7*

14*

16*

19*

20*

22*

24*

25*

27*

29*

33*

34*

38*

39*

22 of 100

B+ trees: insert 8

17

24

13

30

Root Node

2*

3*

5*

7*

14*

16*

19*

20*

22*

24*

25*

27*

29*

33*

34*

38*

39*

8*

23 of 100

B+ trees: insert 8

Find the correct leaf node

17

24

13

30

Root Node

2*

3*

5*

7*

14*

16*

19*

20*

22*

24*

25*

27*

29*

33*

34*

38*

39*

8*

24 of 100

B+ trees: insert 8

Find the correct leaf node

17

24

13

30

Root Node

2*

3*

5*

7*

14*

16*

19*

20*

22*

24*

25*

27*

29*

33*

34*

38*

39*

8*

25 of 100

B+ trees: insert 8

Find the correct leaf node

Split leaf (if not enough room) into two leaves with d and d+1 entries

17

24

13

30

Root Node

14*

16*

19*

20*

22*

24*

25*

27*

29*

33*

34*

38*

39*

2*

3*

5*

7*

8*

26 of 100

B+ trees: insert 8

Find the correct leaf node

Split leaf (if not enough room) into two leaves with d and d+1 entries
Copy up the middle key to inner node (since leaf nodes have data)

17

24

13

30

Root Node

14*

16*

19*

20*

22*

24*

25*

27*

29*

33*

34*

38*

39*

5*

7*

8*

2*

3*

5

27 of 100

B+ trees: insert 8

If inner node is full, split the inner node into two and push the middle key up

14*

16*

19*

20*

22*

24*

25*

27*

29*

33*

34*

38*

39*

5*

7*

8*

2*

3*

5

17

24

13

30

28 of 100

B+ trees: insert 8

If inner node is full, split the inner node into two and push the middle key up

14*

16*

19*

20*

22*

24*

25*

27*

29*

33*

34*

38*

39*

5*

7*

8*

2*

3*

5

17

24

13

30

29 of 100

B+ trees: insert 8

If inner node is full, split the inner node into two and push the middle key up

30

24

14*

16*

19*

20*

22*

24*

25*

27*

29*

33*

34*

38*

39*

5*

7*

8*

2*

3*

5

17

13

30 of 100

B+ trees: insert 8

If inner node is full, split the inner node into two and push the middle key up

17

30

24

14*

16*

19*

20*

22*

24*

25*

27*

29*

33*

34*

38*

39*

5*

7*

8*

2*

3*

5

13

31 of 100

B+ trees: insert 8

If inner node is full, split the inner node into two and push the middle key up

17

30

24

14*

16*

19*

20*

22*

24*

25*

27*

29*

33*

34*

38*

39*

5*

7*

8*

2*

3*

13

5

32 of 100

B+ trees: Insertion Steps Summary

Find correct leaf L
Put data entry into L
If L has enough space, we’re done!
Otherwise, split L into two nodes: L and L₂

Copy up middle key to inner node and add references
If the inner node is full, split the inner node into two, and push up middle key; repeat as needed

33 of 100

Worksheet Q1

34 of 100

Worksheet #1a

What is the maximum number of insertions we can do without changing the height of the tree?

35 of 100

Worksheet #1a

What is the maximum number of insertions we can do without changing the height of the tree?

12. We could insert 12, 25, 44, 81, 80, 78, 76, 79, 77, 75, 74, 73.

36 of 100

Worksheet #1a

What is the maximum number of insertions we can do without changing the height of the tree?

More generally: assuming duplicates are allowed (or keys are not constrained to be integers), you can find the max number of keys a tree of the same height/order can store, and subtract the current number of keys

37 of 100

Worksheet #1a

Maximum number of data entries a B+ tree with height h can hold: (2d * (2d+1)^h)

each inner node for every level has a maximum fanout of (2d+1)
each inner node can contain a maximum of 2d data entries

(2 * d) * (2 * d+ 1)^h = (2 * 1) * (2 * 1 + 1)² = 18

18 (max) - 6 (number of values in tree given) = 12 inserts

38 of 100

Worksheet #1b

What is the minimum number of keys you could insert to change the height of the tree?

39 of 100

Worksheet #1b

What is the minimum number of keys you could insert to change the height of the tree?

3. You could insert 1, 4, 5.

40 of 100

Worksheet #1b

34

6

21

50

2

3

11

43

24

72

Insert 1

1

41 of 100

Worksheet #1b

34

6

21

50

2

3

11

43

24

72

Insert 1

1

42 of 100

Worksheet #1b

34

6

21

50

2

3

11

43

24

72

Insert 1

1

2

43 of 100

Worksheet #1b

34

21

50

2

3

11

43

24

72

Insert 1

1

6

2

44 of 100

Worksheet #1b

34

21

50

2

3

11

43

24

72

Insert 1

1

6

2

45 of 100

Worksheet #1b

6

34

50

2

3

11

43

24

72

Insert 1

1

21

2

46 of 100

Worksheet #1b

6

34

50

2

3

11

43

24

72

Insert 4

1

21

2

4

47 of 100

Worksheet #1b

6

34

50

3

11

43

24

72

Insert 4

1

21

2

4

2

48 of 100

Worksheet #1b

6

34

50

3

11

43

24

72

Insert 4

1

21

2

3

4

2

49 of 100

Worksheet #1b

6

34

50

3

11

43

24

72

Insert 5

1

21

2

3

4

2

5

50 of 100

Worksheet #1b

6

34

50

11

43

24

72

Insert 5

1

21

2

3

4

2

5

3

4

51 of 100

Worksheet #1b

6

34

50

11

43

24

72

Insert 5

1

21

3

4

2

5

3

2

52 of 100

Worksheet #1b

6

34

50

11

43

24

72

Insert 5

1

21

4

2

5

3

2

3

53 of 100

Worksheet #1b

34

50

11

43

24

72

Insert 5

1

21

4

2

5

3

2

3

6

54 of 100

Index Types

55 of 100

How is data stored in the index?

Alternative 1: store actual records in the index

We can’t do this efficiently if we have multiple indices on the table (need to keep multiple copies)

Alternative 2: store <key, recordId> in the index
Alternative 3: store <key, list of matching RecordIDs>

More compact than Alternative 2 if we have a lot of duplicates

56 of 100

Alternative 1 Index (B+ Tree)

Record contents are stored in the index file

No need to follow pointers

17

5

24

(2, Joe)

(3, Jim)

(5, Kay)

(7, Dan)

(20, Tim)

Root Node

(24, Kit)

Data Entries

Interior Nodes

uid	name
2	Joe
3	Jim
5	Kay
7	Dan
20	Tim
24	Kit

57 of 100

Alternative 2 Index

Alternative 2: By Reference, <k, rid of matching data record>

uid	name
2	Joe
3	Jim
5	Kay
7	Dan
20	Tim
24	Kit

(2, Joe)

(3, Jim)

(5, Kay)

(7, Dan)

(20, Tim)

(24, Kit)

17

5

24

(2, [1,1])

(3, [1,2])

(5, [2,1])

(7, [2,2])

(20, [3,1])

Root Node

(24, [3,2])

Data Entries

Interior Nodes

Index File

Index Contains

(Key, Record Id) Pairs

58 of 100

Alternative 3 Index

Alternative 3: By List of references, <k, list of rids of matching data records>

Alternative 3 more compact than alternative 2

For very large rid lists, single data entry spans multiple blocks

(2, Joe)

(2, Jim)

(2, Kay)

(3, Dan)

(3, Tim)

(20, Kit)

17

5

24

(2, {[1,1], [1,2], [2, 1]}

(3, {[2,2], [3, 1]})

(20, {3, 2}])

Root Node

…

Data Entries

Interior Nodes

Index File

Index Contains

(Key, {list of record Id}) Pairs

Key	Record Id
2	{[1,1], [1,2], [1,3]}
3	4

…

59 of 100

Clustering

Property of Alt 2, 3 Indexes
Clustered index: the actual data is (roughly) sorted in order of the search key
Unclustered index: the actual data is not in order of the search key

60 of 100

Clustering

Unclustered

Clustered

I/O Cost:

~ 1 I/O per record

~ 1 I/O per page of records

61 of 100

Note on Full Scans and B+ Trees

During full scans of B+ Trees, we DO NOT include the IO cost to traverse down the B+ tree and find the first data page
Cost to full scan = # of data pages
Ex. For this tree (assume alternative 1), full scan cost is 5 and NOT 1 + 5 = 6

62 of 100

Worksheet Q2

63 of 100

Worksheet #2a

Is it possible to have two clustered indices on separate columns?

64 of 100

Worksheet #2a

Is it possible to have two clustered indices on separate columns?

Yes, but you would generally have to store two copies of the data (and keep both up to date).

Special case: if the search key for one index is a subset of the search key for the other (e.g. index 1 on sid, index 2 on (sid, name)), then we can have just one copy (sorted on (sid, name)).

65 of 100

Worksheet #2b

Assume the table takes up 12 MB on disk (1 MB = 1024 KB) and that page size is 64KB. (This includes extra space allocated for future insertions.)

We want to scan all the records in Submissions. How many I/Os will this operation take?

CREATE TABLE Submissions (

record_id integer UNIQUE,

assignment_id integer,

student_id integer,

time_submitted integer,

grade_received byte,

comment text,

regrade_request text,

PRIMARY KEY(assignment_id, student_id)

);

CREATE INDEX SubmissionLookupIndex

ON Submissions (assignment_id, student_id);

2. Suppose we have an alternative 2 unclustered index on (assignment_id, student_id) with a height of 3 (one must traverse 3 index pages to reach any leaf page). Here's the schema:

66 of 100

Worksheet #2b

Assume the table takes up 12 MB on disk (1 MB = 1024 KB) and that page size is 64KB. (This includes extra space allocated for future insertions.)

We want to scan all the records in Submissions. How many I/Os will this operation take?

CREATE TABLE Submissions (

record_id integer UNIQUE,

assignment_id integer,

student_id integer,

time_submitted integer,

grade_received byte,

comment text,

regrade_request text,

PRIMARY KEY(assignment_id, student_id)

);

CREATE INDEX SubmissionLookupIndex

ON Submissions (assignment_id, student_id);

2. Suppose we have an alternative 2 unclustered index on (assignment_id, student_id) with a height of 3 (one must traverse 3 index pages to reach any leaf page). Here's the schema:

To do a full table scan, we read each page into memory once. There are 12 * 1024/64 = 192 pages in the table, so that’s 192 I/Os (all page reads).

67 of 100

Worksheet #2c

Assume the table takes up 12 MB on disk (1 MB = 1024 KB) and that page size is 64KB. (This includes extra space allocated for future insertions.)

How many I/Os will this operation take?

UPDATE Students SET grade_received=85 WHERE assignment_id=20 AND student_id=12345;

CREATE TABLE Submissions (

record_id integer UNIQUE,

assignment_id integer,

student_id integer,

time_submitted integer,

grade_received byte,

comment text,

regrade_request text,

PRIMARY KEY(assignment_id, student_id)

);

CREATE INDEX SubmissionLookupIndex

ON Submissions (assignment_id, student_id);

2. Suppose we have an alternative 2 unclustered index on (assignment_id, student_id) with a height of 3 (one must traverse 3 index pages to reach any leaf page). Here's the schema:

68 of 100

Worksheet #2c

Assume the table takes up 12 MB on disk (1 MB = 1024 KB) and that page size is 64KB. (This includes extra space allocated for future insertions.)

How many I/Os will this operation take?

UPDATE Students SET grade_received=85 WHERE assignment_id=20 AND student_id=12345;

Read the page into memory: 3 page reads for the index + 1 page read for the leaf page

+ 1 page read for the data page (b/c alt. 2)

Write the modification in memory and then flush the page back to disk: 1 page write for the data page

This costs us a total of 6 disk I/Os.

CREATE TABLE Submissions (

record_id integer UNIQUE,

assignment_id integer,

student_id integer,

time_submitted integer,

grade_received byte,

comment text,

regrade_request text,

PRIMARY KEY(assignment_id, student_id)

);

CREATE INDEX SubmissionLookupIndex

ON Submissions (assignment_id, student_id);

2. Suppose we have an alternative 2 unclustered index on (assignment_id, student_id) with a height of 3 (one must traverse 3 index pages to reach any leaf page). Here's the schema:

69 of 100

Worksheet #2d

Assume the table takes up 12 MB on disk (1 MB = 1024 KB) and that page size is 64KB. (This includes extra space allocated for future insertions.)

In the worst case, how many I/Os does it take to perform an equality search on grade_received?

CREATE TABLE Submissions (

record_id integer UNIQUE,

assignment_id integer,

student_id integer,

time_submitted integer,

grade_received byte,

comment text,

regrade_request text,

PRIMARY KEY(assignment_id, student_id)

);

CREATE INDEX SubmissionLookupIndex

ON Submissions (assignment_id, student_id);

2. Suppose we have an alternative 2 unclustered index on (assignment_id, student_id) with a height of 3 (one must traverse 3 index pages to reach any leaf page). Here's the schema:

70 of 100

Worksheet #2d

Assume the table takes up 12 MB on disk (1 MB = 1024 KB) and that page size is 64KB. (This includes extra space allocated for future insertions.)

In the worst case, how many I/Os does it take to perform an equality search on grade_received?

In the worst case, any record can match the grade_received predicate. Therefore, we must check every record of the table. This is equivalent to performing a table scan, and we would read every page, requiring 192 page reads.

CREATE TABLE Submissions (

record_id integer UNIQUE,

assignment_id integer,

student_id integer,

time_submitted integer,

grade_received byte,

comment text,

regrade_request text,

PRIMARY KEY(assignment_id, student_id)

);

CREATE INDEX SubmissionLookupIndex

ON Submissions (assignment_id, student_id);

2. Suppose we have an alternative 2 unclustered index on (assignment_id, student_id) with a height of 3 (one must traverse 3 index pages to reach any leaf page). Here's the schema:

71 of 100

Bulkloading

72 of 100

Bulkloading Procedure

Creating a B+ tree from scratch is very costly if we insert every node because we have to traverse from the top of the tree to the bottom each time. Instead, use bulkloading:

Sort the data pages by the given key
Given a fill factor f, fill leaves with the data until the fill factor. If the leaf node overflows, add the overflowing value to the parent node + start filling in a new leaf
If the parent node overflows, split the parent node into two groups:

Keep d entries to L₁ and d + 1 entries to L₂
Move the first entry in L₂ to parent since the parent overflowed

Adjust pointers

73 of 100

Worksheet Q3

74 of 100

Worksheet #3

Suppose we were to create an order d=2 B+ tree via bulk-loading with a fill factor of 3/4. We insert keys with all integer values from 1-16 in order.

Here, fill factor specifies the fill factor for leaves only; inner nodes should be filled up to full and split in half exactly.

Draw out the final B+ tree. What is its height?

75 of 100

1

Bulk Loading: d = 2, f = 3/4 * GREY indicates an INTERMEDIATE step, which is not a valid state

Inserting 1-16 in order into an empty B+ tree

76 of 100

1

2

Bulk Loading: d = 2, f = 3/4 * GREY indicates an INTERMEDIATE step, which is not a valid state

77 of 100

1

2

3

Bulk Loading: d = 2, f = 3/4 * GREY indicates an INTERMEDIATE step, which is not a valid state

78 of 100

1

2

3

4

Bulk Loading: d = 2, f = 3/4 * GREY indicates an INTERMEDIATE step, which is not a valid state

Leaf node has exceeded fill factor of 3/4 (since there are more than 3 entries)

79 of 100

1

2

3

4

Bulk Loading: d = 2, f = 3/4 * GREY indicates an INTERMEDIATE step, which is not a valid state

Split leaf node

80 of 100

1

2

3

4

5

4

Bulk Loading: d = 2, f = 3/4 * GREY indicates an INTERMEDIATE step, which is not a valid state

81 of 100

1

2

3

4

5

6

4

Bulk Loading: d = 2, f = 3/4 * GREY indicates an INTERMEDIATE step, which is not a valid state

82 of 100

1

2

3

4

5

6

7

4

Bulk Loading: d = 2, f = 3/4 * GREY indicates an INTERMEDIATE step, which is not a valid state

Leaf node has exceeded fill factor of 3/4 (since there are more than 3 entries)

83 of 100

1

2

3

4

5

6

4

7

Bulk Loading: d = 2, f = 3/4 * GREY indicates an INTERMEDIATE step, which is not a valid state

Split leaf node

84 of 100

1

2

3

4

5

6

4

7

8

Bulk Loading: d = 2, f = 3/4 * GREY indicates an INTERMEDIATE step, which is not a valid state

85 of 100

1

2

3

4

5

6

4

7

8

9

Bulk Loading: d = 2, f = 3/4 * GREY indicates an INTERMEDIATE step, which is not a valid state

86 of 100

1

2

3

4

5

6

4

7

8

9

10

Bulk Loading: d = 2, f = 3/4 * GREY indicates an INTERMEDIATE step, which is not a valid state

Leaf node has exceeded fill factor of 3/4 (since there are more than 3 entries)

87 of 100

1

2

3

4

5

6

4

7

10

7

8

9

10

Bulk Loading: d = 2, f = 3/4 * GREY indicates an INTERMEDIATE step, which is not a valid state

Split leaf node

88 of 100

1

2

3

4

5

6

4

7

10

7

8

9

10

11

Bulk Loading: d = 2, f = 3/4 * GREY indicates an INTERMEDIATE step, which is not a valid state

89 of 100

1

2

3

4

5

6

4

7

10

7

8

9

10

11

12

Bulk Loading: d = 2, f = 3/4 * GREY indicates an INTERMEDIATE step, which is not a valid state

90 of 100

1

2

3

4

5

6

4

7

10

7

8

9

10

11

12

13

Bulk Loading: d = 2, f = 3/4 * GREY indicates an INTERMEDIATE step, which is not a valid state

Leaf node has exceeded fill factor of 3/4 (since there are more than 3 entries)

91 of 100

Bulk Loading: d = 2, f = 3/4 * GREY indicates an INTERMEDIATE step, which is not a valid state

Split leaf node

1

2

3

4

5

6

4

7

10

13

7

8

9

10

11

12

13

92 of 100

Bulk Loading: d = 2, f = 3/4 * GREY indicates an INTERMEDIATE step, which is not a valid state

1

2

3

4

5

6

4

7

10

13

7

8

9

10

11

12

13

14

93 of 100

Bulk Loading: d = 2, f = 3/4 * GREY indicates an INTERMEDIATE step, which is not a valid state

1

2

3

4

5

6

4

7

10

13

7

8

9

10

11

12

13

14

15

94 of 100

Bulk Loading: d = 2, f = 3/4 * GREY indicates an INTERMEDIATE step, which is not a valid state

1

2

3

4

5

6

4

7

10

13

7

8

9

10

11

12

13

14

15

16

Leaf node has exceeded fill factor of 3/4 (since there are more than 3 entries)

95 of 100

Bulk Loading: d = 2, f = 3/4 * GREY indicates an INTERMEDIATE step, which is not a valid state

1

2

3

4

5

6

4

7

10

13

7

8

9

10

11

12

13

14

15

Split leaf node

Parent node is full (since there are more than 4 entries)

16

96 of 100

Bulk Loading: d = 2, f = 3/4 * GREY indicates an INTERMEDIATE step, which is not a valid state

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

Split parent node into 2 nodes with d = 2 entries each

16

4

7

10

13

16

97 of 100

Bulk Loading: d = 2, f = 3/4 * GREY indicates an INTERMEDIATE step, which is not a valid state

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

Split parent node into 2 nodes with d = 2 entries each

16

4

7

13

16

10

98 of 100

Worksheet #3

The final height of the tree would be 2.

99 of 100

Summary

Inner nodes contain up to 2d values, and have a maximum fanout of 2d+1

Maximum number of data entries a B+ tree with height h can hold: (2d * (2d+1)^h)

B+ tree insertion:

Find correct leaf node L and insert into L if there is space
if L is full:

split L into L1 and L2
if L is a leaf node, copy up middle key to inner node
if L is an inner node, push up middle key

B+ tree indices

Alternative 1: Record contents are stored in the index file
Alternative 2: By Reference, <k, rid of matching data record>
Alternative 3: By List of references, <k, list of rids of matching data records>

100 of 100

Attendance Link

https://cs186berkeley.net/attendance