技術 約7分で読めます

検索を速くするデータ構造総まとめ - Trie, 転置インデックス, 接尾辞配列, ダブル配列

データ構造 アルゴリズム 検索 全文検索

検索といっても色々ある。完全一致、前方一致、部分文字列検索、あいまい検索、全文検索…。「どんな検索をしたいか」で最適なデータ構造は変わってくる。

めんどくさいときはDBに放り込んでしまえばいいかとか割と端折ってしまうが、本来あまりよくない。

そこで、検索系処理で使われる主要なデータ構造を10種類まとめた。
それぞれの仕組み、得意な検索タイプ、計算量、実際の使用例を整理している。

検索タイプの分類

まず検索の種類を整理しておく。

検索タイプ説明例
完全一致キーと完全に一致辞書引き、ハッシュテーブル
前方一致先頭が一致オートコンプリート「abc…」
部分文字列途中に含むgrep、Ctrl+F
あいまい検索編集距離が近いスペル修正「teh → the」
全文検索単語を含む文書を探すGoogle検索、サイト内検索
範囲検索値の範囲「価格が1000〜2000円」

Trie（トライ）

文字ごとにノードを辿る木構造。前方一致検索の基本形。

        root
       / | \
      c  d  t
      |  |  |
      a  o  o
     /|  |  |
    t r  g  p

「cat」「car」「dog」「top」を格納したTrie。

得意: 前方一致、オートコンプリート、共通接頭辞の検出

計算量: O(m)　※mはキー長

欠点: メモリ効率が悪い。各ノードが子へのポインタを持つため、スパースな木になりがち。

使用例: IMEの変換候補、URLルーティング、IPアドレス検索（Patricia Trie）

ダブル配列（Double-Array Trie）

Trieを配列2本で表現する高速化手法。MeCabやSudachiなど形態素解析器の内部で使われている。

インデックス:  0   1   2   3   4   5   6   7
BASE:        [-   1   3   -   5   -   -   2 ]
CHECK:       [-   0   1   -   2   -   -   1 ]

仕組み:

  • BASE[s] + c = t で遷移先を計算
  • CHECK[t] = s で遷移元を検証

状態sから文字コードcで遷移するとき:

  1. t = BASE[s] + c を計算
  2. CHECK[t] == s なら遷移成功、そうでなければその文字での遷移は存在しない

得意: 辞書引き、形態素解析（大量の単語を高速に検索）

計算量: O(m)　※Trieと同じだが、キャッシュ効率が良い

欠点: 構築が複雑。動的な追加・削除が苦手（配列の再配置が必要）。

使用例: MeCab、Sudachi、ATOK、Google日本語入力

転置インデックス（Inverted Index）

「単語 → その単語を含む文書のリスト」というマッピング。全文検索の基本。

【元データ】
Doc1: "猫が寝ている"
Doc2: "犬が走っている"
Doc3: "猫が走っている"

【転置インデックス】
猫   → [Doc1, Doc3]
犬   → [Doc2]
寝   → [Doc1]
走   → [Doc2, Doc3]

「転置」と呼ばれるのは、普通の「文書→単語」の関係を逆転（invert）させているから。

得意: 全文検索、AND/OR検索、フレーズ検索

計算量: O(1)でポスティングリスト取得。AND検索はリストのマージでO(n+m)。

付随情報:

  • TF（単語の出現回数）
  • IDF（逆文書頻度）
  • 位置情報（フレーズ検索用）

使用例: Elasticsearch、Apache Lucene、Pagefind、Algolia

接尾辞配列（Suffix Array）

文字列の全接尾辞をソートした配列。部分文字列検索を二分探索で実現する。

文字列: "banana"

接尾辞:
0: banana
1: anana
2: nana
3: ana
4: na
5: a

ソート後（接尾辞配列）:
[5, 3, 1, 0, 4, 2]
 a  ana anana banana na nana

「ana」を検索するとき、ソート済みなので二分探索できる。

得意: 部分文字列検索、最長共通部分文字列

計算量: O(m log n)で検索　※mはパターン長、nは文字列長

メリット: 接尾辞木より省メモリ（ポインタがない）

使用例: DNA配列検索、大規模テキスト検索、bzip2圧縮

接尾辞木（Suffix Tree）

全接尾辞を圧縮したTrie。接尾辞配列より高機能だがメモリを食う。

文字列: "banana$"

        root
       /    \
      a      banana$
     / \
   na$  $
   |
  na$

共通接頭辞を圧縮して1つのエッジにまとめる。

得意: 部分文字列検索、最長共通部分文字列、最長繰り返し部分列

計算量: O(m)で検索　※接尾辞配列より速い

欠点: メモリ消費が大きい（元文字列の10〜20倍）

使用例: バイオインフォマティクス（DNA・タンパク質配列解析）

BK木（Burkhard-Keller Tree）

編集距離（レーベンシュタイン距離）に基づく木構造。あいまい検索に特化。

        "book"
       /  |  \
      1   2   3
     /    |    \
  "cook" "back" "banana"

ルートからの編集距離でノードを配置する。

仕組み:

  • 検索語との編集距離がd以下の単語を探すとき
  • 現在ノードとの編集距離がkなら、子のうちk-d〜k+dの枝だけを探索

三角不等式により、探索範囲を大幅に枝刈りできる。

得意: あいまい検索、スペル修正、類似文字列検索

計算量: 編集距離の閾値に依存。閾値が小さいほど高速。

使用例: スペルチェッカー、「もしかして」機能

n-gramインデックス

文字列をn文字ずつ分割してインデックスを作る。日本語の部分一致検索でよく使われる。

文字列: "検索エンジン"

2-gram（bigram）:
["検索", "索エ", "エン", "ンジ", "ジン"]

3-gram（trigram）:
["検索エ", "索エン", "エンジ", "ンジン"]

得意: 部分一致検索、日本語検索（形態素解析なしで検索可能）

計算量: O(1)でn-gramのポスティングリスト取得

欠点: インデックスサイズが大きい（元データの数倍）

使用例: PostgreSQL pg_trgm、MySQL ngram parser、日本語全文検索の補助

Bloom Filter

「存在しない」を高速に判定する確率的データ構造。偽陽性はあるが偽陰性はない。

ビット配列: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

"cat"を追加（ハッシュ値: 2, 5, 8）:
           [0, 0, 1, 0, 0, 1, 0, 0, 1, 0]

"dog"を追加（ハッシュ値: 1, 5, 9）:
           [0, 1, 1, 0, 0, 1, 0, 0, 1, 1]

仕組み:

  • 追加: k個のハッシュ関数でビットを立てる
  • 検索: k個のビットがすべて1なら「たぶんある」、1つでも0なら「確実にない」

得意: 存在判定の前処理、不要なディスクアクセスの回避

計算量: O(k)　※kはハッシュ関数の数

特性: 偽陽性率は調整可能（ビット配列を大きくすれば下がる）

使用例: LevelDB/RocksDBのSSTable検索前フィルタ、キャッシュのnegative lookup、スパムフィルタ

B+木（B+ Tree）

RDBのインデックスで使われるバランス木。リーフノードがリンクで繋がっている。

        [30 | 60]
       /    |    \
   [10|20] [40|50] [70|80|90]
     ↓       ↓         ↓
   リーフ → リーフ → リーフ（リンクで連結）

仕組み:

  • 内部ノードはキーと子へのポインタを持つ
  • リーフノードに実データ（またはデータへのポインタ）がある
  • リーフ同士がリンクで繋がっている → 範囲スキャンが高速

得意: 範囲検索、ソート済みスキャン、等価検索

計算量: O(log n)で検索・挿入・削除

メリット: ディスクI/Oに最適化（1ノード = 1ページ）

使用例: MySQL InnoDB、PostgreSQL、SQLite、ファイルシステム（NTFS, ext4）

LSM木（Log-Structured Merge Tree）

書き込みを順次追記し、バックグラウンドでマージする構造。書き込みが多いワークロードに強い。

メモリ:     [MemTable] ← 新規書き込み
              ↓ フラッシュ
ディスク:  Level 0: [SST] [SST] [SST]
              ↓ コンパクション
           Level 1: [SST] [SST]
              ↓
           Level 2: [SST]

仕組み:

  1. 書き込みはメモリ上のMemTableに追記（Write-Ahead Logも書く）
  2. MemTableが一定サイズになったらディスクにフラッシュ（SSTable）
  3. SSTはイミュータブル。バックグラウンドでマージ（コンパクション）
flowchart LR
    subgraph Memory
        W[Write] --> MT[MemTable]
        MT --> WAL[WAL]
    end
    subgraph Disk
        MT -->|flush| L0[Level 0]
        L0 -->|compact| L1[Level 1]
        L1 -->|compact| L2[Level 2]
    end
    R[Read] --> MT
    R --> L0
    R --> L1
    R --> L2

読み込み時は、MemTable → Level 0 → Level 1 → … と順に探す。見つかったら終了。

得意: 書き込みが多いワークロード、時系列データ

計算量:

  • 書き込み: O(1) 攤却（シーケンシャルライト）
  • 読み込み: O(log n) × レベル数（複数SSTを走査）

欠点: 読み込みは複数レベルを見る必要があり、B+木より遅い場合がある

使用例: LevelDB、RocksDB、Cassandra、InfluxDB

比較表

データ構造検索タイプ検索計算量メモリ主な用途
Trie前方一致O(m)大オートコンプリート
ダブル配列完全一致/前方O(m)小形態素解析
転置インデックス全文検索O(1)中検索エンジン
接尾辞配列部分文字列O(m log n)小grep, DNA
接尾辞木部分文字列O(m)大文字列解析
BK木あいまい可変中スペル修正
n-gram部分一致O(1)大日本語検索
Bloom Filter存在判定O(k)極小フィルタリング
B+木範囲検索O(log n)中RDBインデックス
LSM木書き込み特化O(log n)×中KVS, 時系列DB

※ mはキー/パターン長、nはデータ数、kはハッシュ関数数

実際のシステムでの組み合わせ

実際のシステムでは、複数のデータ構造を組み合わせて使うことが多い。

Elasticsearch / Apache Lucene:

  • 転置インデックス（テキスト検索）
  • BKD木（数値・地理の範囲検索）
  • FST（辞書の圧縮）

MeCab / Sudachi:

  • ダブル配列（辞書引き）
  • 最小コスト法（最適な形態素列の選択）

Pagefind:

  • 転置インデックス
  • gzip圧縮 + チャンキング（帯域幅最適化）

PostgreSQL:

  • B+木（主要インデックス）
  • GIN（転置インデックス、全文検索）
  • GiST（地理データ、範囲型）
  • BRIN（大規模テーブルのブロック範囲）

LevelDB / RocksDB:

  • LSM木（メイン構造）
  • Bloom Filter（SSTable検索前フィルタ）

Redis:

  • ハッシュテーブル（KVS本体）
  • スキップリスト（ソート済みセット）
  • 基数木（キーのプレフィックス検索）

検索の種類とデータの特性（読み書き比率、データサイズ、クエリパターン）に応じて、適切なデータ構造を選ぶ……がどれを使うか悩むことが多い。
万能な構造はないので、用途に合わせた組み合わせなんだろうなとは思う。
特に検索範囲が広いと計算量が多くなるタイプは使いどころが注意がいる。