File Systems 1: File Indexes with B-Trees 

One way to speed up file access is to use an index, and a common way to create such an index is by using a B-Tree, a particular type of self balancing tree. The structure of B-Trees is introduced, along with examples of how insertions modify the tree. Much of this material is based on content from the book Operating Systems: Internals and Design Principles by William Stallings.