基数木
以下の比較では、キーの長さを k、格納している要素数を n としている。
平衡2分探索木では、検索・挿入・削除には O(log n) の時間がかかるが、基数木では O(k) である。一般に k ≥ log n であるから、これは利点とは見なされないが、平衡2分探索木での比較は常に文字列の比較であり、最悪で O(k) の時間がかかる。特に長い接頭部が共通な文字列を多数格納していると遅くなる。一方、トライ木では比較は文字の比較で定数時間で済み、長さ m の文字列なら m 回の比較が必要となる。基数木は比較回数も少なく、走査するノード数も少ない。
ただし、基数木にはトライ木と同じ欠点がある。これらは、文字列や文字列に写像できるデータしか扱えない。それに対して平衡2分探索木は、順序関係のある任意のデータ型を扱える。これは例えば、大小比較だけが可能だが、シリアライズできないデータ型で問題となる。
ハッシュテーブルは一般に挿入・削除に O(1) の時間しかかからないとされているが、これはキーの操作を定数時間とみなしているためであって、キーの構造を考慮すると変わってくる。キーの長さが k なら、ハッシュテーブルでの挿入・削除には O(k) の時間がかかり、衝突が発生すると処理方式によってはさらに時間がかかる。基数木は最悪でも O(k) で挿入・削除できる。また、基数木では可能な辞書式順序の前後を取り出す操作もハッシュテーブルでは不可能である。