page cache
Memory the operating system or database uses to keep recently read disk blocks, so repeated reads skip the disk.
In more detail
The root and top levels of a busy B-tree are read so often that they almost always sit in the page cache, so a lookup usually costs only one or two real disk reads. This is why B-tree performance in practice is even better than its height suggests.
Related terms
- disk block — The fixed-size unit, typically a few kilobytes, in which data is read from and written to disk.
- B-tree — A balanced search tree whose nodes each hold many sorted keys and have many children, so the tree is very wide and very shallow.
- I/O — Input and output: any time a program reads or writes data outside its own memory, such as files, networks or the terminal.
Taught in
- B-Trees: The Structure Behind Every Database Index — Algorithms & Data Structures for Working Engineers