index
データベースのインデックスは常に更新にさらされます。（略）insertやdelete、 updateといった文をすぐに実行し、大量のデータを動かすこと なく、インデックスの順序を保つ必要があります。
データベースは、2つのデータ構造を組み合わせてこの問題に対処しています。 それが、双方向連結リス]と、検索木です。これら2つのデータ構造で、ほとんどのデータベースのパフォーマンス特性の説明がついてしまいます。 The database combines two data structures to meet the challenge: a doubly-linked list and a search tree. These two structures explain most of the database’s performance characteristics.