以前、UUIDv4はランダムで作られるから、大規模データだとパフォーマンスが悪くなるという話で、DBのインデックス構造におけるハッシュとB木（B-tree）の使い方やそのパフォーマンスについてもう少し調べてみた
ハッシュインデックスとB木（B-tree）インデックスの違い
ハッシュインデックスとB木（B-tree）インデックスの違いをまず調べると
- ハッシュインデックス: IDなどの単一の値を直接一発で検索する際に有効。O(1)の時間で特定のIDのデータを取り出すことができる
- O(1)の時間とは、「定数時間」とも呼ばれ、データの大きさや状況に関わらず、処理にかかる時間が一定であることを意味する
- 具体的には、データが1件であっても100万件であっても、処理にかかる時間が変わらないことを指す
- B木インデックス: 範囲検索や並び替え(ORDER BY)を行う際にはハッシュインデックスでは不十分なため、B木構造を使用する
ページ単位でのデータ取り出しとランダムアクセスの影響
データベースは、記憶領域に保存されているデータを「ページ」と呼ばれるチャンク（例: 16KB単位）で管理している
つまり、1件のレコードを取り出す際も、実際にはそのレコードが含まれるページ全体（16KBなど）がメモリにロードされる
hash / randomアクセスが発生すると、ページ単位でデータを読み込むため、キャッシュの入れ替え（スラッシング）が起きやすくなる
結果として、他の必要なレコードが同じページに存在する可能性は非常に低く、キャッシュ効率が低下する
よくある「最新100件」の取得条件によるキャッシュへの影響
よくある「最新100件」といった条件でデータを取得する際、データベースは16KBのページを100件分読み込むため、1.6MBのデータがキャッシュにロードされる
このような操作を頻繁に行うとキャッシュの入れ替えが頻発し、キャッシュヒット率（キャッシュ内に必要なデータが存在する確率）が大幅に下がり、パフォーマンスが低下する
対策
ランダムアクセスが頻発するシナリオではパフォーマンスに悪影響を及ぼすので、その対策としては以下が挙げられる
- UUIDv4を使わない
- ハッシュインデックスでなるべく済むようにする
- インメモリデータベースを活用する
- 頻繁なランダムアクセスが必要な場合、インメモリデータベース（例: Redis）を使ってホットデータをキャッシュすることで、ディスクアクセスを最小限に抑えることができる
- これにより、ディスクI/Oによるスラッシングを防ぎ、アクセス速度を大幅に向上させることができる
- データの分散とシャーディング
- 大規模なデータセットで頻繁なランダムアクセスが発生する場合、データを複数のサーバーやノードに分散（シャーディング）して処理負荷を分散させる
- これにより、各ノードのキャッシュの効率が改善され、I/O負荷を分散できる
- パーティショニングの活用
- テーブルパーティショニングを行うことで、特定の範囲にアクセスするクエリを最適化し、パーティションごとに効率的にデータを取得できるようにすることが可能
まとめ
ハッシュは特定のIDを直接取得するには高速だが、実際のアプリケーションでは範囲検索や並び替えが多く必要なため、B木インデックスが適している
しかし、B木でのランダムアクセスはページ単位でデータを読み込むため、キャッシュの効率が下がりやすく、特に大量のデータ取得が発生するとキャッシュヒット率が悪化しやすいという問題が生じることがわかった
