Memory is slow, Disk is fast

Big O notation is a simplification that omits key details. While it suggests O(√n) scales better than O(log n), disk-based algorithms can outperform in-RAM data structures. A sorted set of 8-byte keys with four transactions (insert, delete, search, and at(i)) demonstrates this.

The simplest solution, an ordered array, uses binary search (O(log n)) and direct access (O(1)). However, inserting requires moving half the array, an O(n) operation. Inserting a billion nodes would demand 4 GiB per insertion.

A linked list avoids shifting elements, with O(1) insert/delete but O(n) search and at(i). Branching the list into a binary search tree (AVL tree) ensures log n performance for all operations, but at the cost of increased RAM usage (288 MiB for 2 billion nodes vs. 32 MiB for the sorted array).

To mitigate the insert/delete penalty, DiskArray splits keys into small extents. Indexes point to extents, allowing inserts/deletes to affect only a portion of the data. Extents are stored on disk, with the index in RAM and a buffer pool for I/O. Despite the overhead of AVL trees, DiskArray's brute-force approach offers a practical alternative for handling large datasets.