Часть 0: Размышления о хранении данных
Разработчики предъявляют высокие требования к базам данных: максимальная надежность (ничего из того, что было записано не должно быть утеряно ни при каких обстоятельствах), и, одновременно, максимальная производительность при различных видах нагрузки (Запись/Чтение или OLTP/OLAP). Достичь этих требований может быть не просто. Давайте попробуем разобраться, как это делает MySQL.

Размышляя о базе данных, легко представить таблицу базы данных как HashMap/BinaryTree, отображающие первичный ключ (primary key) в структурированные записи с данными. Такое хранилище может работать in memory. Но, как только мы захотим записать данные на диск, придется использовать какие-то алгоритмы во внешней памяти. Просто положить наш HashMap на диск не получится, потому что память и диски слишком разные: чтение/запись диска производится блоками, latency диска больше чем у RAM, а еще нельзя будет воспользоваться обычными указателями и аллокаторами памяти — все это придется заменить самостоятельно.