他のデータ構造との比較

ウィキペディア小見出し辞書

他のデータ構造との比較

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/03/23 05:48 UTC 版)

「基数木」の記事における「他のデータ構造との比較」の解説

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

他のデータ構造との比較

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/11/26 05:33 UTC 版)

「表 (データベース)」の記事における「他のデータ構造との比較」の解説

関係データベース以外（階層型データモデルなど）では、表にほぼ相当するものとして構造化ファイルがあり、レコードが表の行に相当し、レコードのカラムが列に相当する。 表計算ソフトとは異なり、各フィールドのデータ型は、表を表すスキーマで定義されているのが普通である。関係データベースによっては、フィールドのデータ型定義が厳密でないものもある。