パトリシアトライ
木構造の一種

文字列の検索に向いている

O(k): k = 文字列長

prefix検索・最長一致検索

キーワード検出(ニコニコ大百科)

DBMではB+木採用が多い