📘 データベースインデックスと双方向連結リストの必要性

📌 背景

データベースにおけるインデックスは、検索を高速化するために「論理的な順序」を保ちながらデータを扱います。
ただし、物理的な順序を常に維持すると、INSERT や DELETE のたびに大規模なデータ移動が必要となり、非常に非効率です。

この問題を解決するために B-Tree が利用され、そのリーフノードは 双方向連結リスト で接続されています。

---

📌 単方向連結リストと双方向連結リストの違い

単方向連結リスト (Singly Linked List)

• 各ノードは next のみを保持
• 前から後ろへ一方向にしか辿れない
• 欠点:
  • ORDER BY ... DESC のように逆順で結果を取得する場合、末尾まで辿らなければならない
  • 範囲検索の柔軟性が低い

双方向連結リスト (Doubly Linked List)

• 各ノードは prev と next の両方を保持
• 前後どちらの方向にも辿れる
• 利点:
  • 昇順 (ASC) / 降順 (DESC) の両方を効率的にサポート
  • 範囲検索で開始位置に応じて柔軟に処理可能

---

📌 DBインデックスでの利用方法

• 探索: B-Tree 構造で高速に対象データを特定
• 順序維持: リーフノード同士を双方向連結リストで接続
• 結果取得:
  • ASC → 先頭リーフから順次読み込み
  • DESC → 末尾リーフから逆方向に読み込み

-- 昇順
SELECT * FROM users ORDER BY id ASC LIMIT 10;

-- 降順
SELECT * FROM users ORDER BY id DESC LIMIT 10;

これにより、インデックスは 検索性能 + 両方向の範囲探索 を効率的に実現できます。

---

✅ まとめ

• 物理的順序を維持するのは高コスト → DBMS は B-Tree + 双方向連結リストで解決
• 双方向連結リストにより、ASC/DESC 双方向の探索 や 範囲検索の効率化 が可能
• インデックスは「ただ検索を速くする」だけではなく、順序付きのデータアクセスを最適化する仕組み である