Скачать или смотреть B-trees: Samuel's tutorial

Samuel's tutorial on B-trees (memory hierarchy, disk accesses, search, insertion and deletion).

Timestamps:
00:00 - B-Trees: Samuel's Guide
01:57 - Precursor: Memory Hierarchy/External Memory
05:17 - B-trees and Counting Disk Accesses
06:34 - B-tree Definition
09:58 - B-tree Search
12:43 - B-tree Insertion
14:41 - B-tree Insertion - split_child()
17:02 - B-tree Insertion - split_root()
18:04 - B-tree Insertion - insert_not_full()
21:00 - B-tree Deletion
23:02 - B-tree Deletion - Case 1
23:35 - B-tree Deletion - Case 2
26:23 - B-tree Deletion - Case 3 (3a)
28:56 - B-tree Deletion - Case 3 (3b)
30:04 - B-tree Deletion - merge_children()
31:29 - B-tree Deletion - Complexity

Detailed description:

This video offers a brief guide to B-trees. First, we describe their introduction in 1970 (and their name), together with their complexity for search, insertion and deletion operations - O(log n).

We then provide some background on memory hierarchy and the use of external memory in a computer, highlighting the importance of blocks for efficient access on HDDs/SSDs.

The great value of B-trees comes from the fact that we can pack many keys into each node while staying within a block, allowing for "shallow-but-wide" trees that require few disk accesses to traverse. When analysing B-trees, our complexity accounting tracks both CPU time and disk accesses.

We then discuss the properties that define B-trees and show why the height of a B-tree is guaranteed to grow logarithmically. Next, we describe B-tree search and provide Python code to implement it.

Our next focus is B-tree insertion, which uses a "fix-then-insert" strategy to insert keys in a single pass down the tree. We walk through each of the helper functions involved in implementing this functionality.

Finally, we discuss B-tree deletion and the various cases that must be handled. We conclude with a discussion of the complexity of B-tree deletion, and briefly note the existence of B-tree variants (the B+-tree and the B*-tree).

Corrections:
07:20 - This part of the definition is not quite right. See further notes below.

Correction to part iii of the B-tree definition at 07:20:
The inequality should be replaced by three inequalities (in the following j ranges over valid indices of keys):
u.keys[i] \leq u.children[i+1].keys[j] \leq u.keys[i+1]
u.children[0].keys[j] \leq u.keys[0]
u.keys[-1] \leq u.children[-1].keys[j]
Here "\leq" means "Less Than or Equal To" (YouTube descriptions don't allow the use of angled brackets). The definition has been updated in the slides (linked below).

Topics: #datastructures #btree #coding

Python code for a lightweight implementation of B-trees can be found here: https://github.com/albanie/algorithms...

Slides (pdf): https://samuelalbanie.com/files/diges...

References for papers mentioned in the video can be found at
http://samuelalbanie.com/digests/2022...

Recommended further reading on this topic:
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to algorithms. MIT press. https://mitpress.mit.edu/978026204630...
L. Xinyu, "Elementary Algorithms", Chap. 7, https://github.com/liuxinyu95/AlgoXY (2022)