I am a Professor in the Computer Science department at the University of Cambridge. Through this channel I welcome anyone in the world to attend my lectures. This video is part of my first-year Algorithms course.
The B-Tree is a search tree optimised for the case in which there are so many keys to be stored that the whole t
ree won’t fit in RAM. Since accessing a byte on disk can be about 100,000 times slower than accessing a byte in memory, it makes sense to design the data structure so as to minimize the number of disk accesses. This is done by building a very shallow search tree, which in turn is achieved by dramatically increasing the branching factor of each node.
The logical structure of the B-Tree is a generalisation of that of the 2-3-4 tree we saw in a previous video. Historically, the B-Tree came first, then it was ported to memory as the 2-3-4 tree, and then the 2-3-4 tree was transformed into a balanced binary tree with the Red-Black construction which we also saw in a previous video.
In this video I describe the structure of the B-tree and explain in detail how to perform insertions and deletions in it.
Many thanks to those of you who are giving thumbs up to these videos and subscribing to the channel. Your support is greatly appreciated and it causes Youtube to offer this material to more viewers who might like it.
Course web page:
https://www.cl.cam.ac.uk/teaching/current/Algorithms/
Course handout:
https://www.cl.cam.ac.uk/teaching/2021/Algorithms/2020-2021-stajano-algs-handout.pdf
My home page:
http://frank.stajano.com
Add comment