人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

データベースについての質問です。

一般的にRDBMSではインデックスにB+木を利用していると思います。良くわからないのは、キーが文字列で長い場合です。単純にキーをノードに格納すると、キーがノードの容量の多くを占めます。このため、ノードに格納できる要素数が少なくなり、時間的・空間的な効率が悪化するように思います。RDBMSでは、どのようにこの問題を解決しているのでしょうか?

以下いずれかの形式に沿って回答をお願いします。
簡単な解説も加えていただけると助かります。

1. 文字列をキーとするインデックスで効率の良いXXというアルゴリズムがあり、一般的にRDBMSではそれを利用している

2. XXというRDBMSでは、XXのようなアプローチを採用している

3. 一般的にRDBMSでは長いキーに特に対策をしていない

なお、MySQLのcol_name(length)のようにプリフィックス長でキーを切り詰める方法や、PostgreSQLのpg_trgmモジュールのようにn-gramインデックスを作る方法は、回答不要です。

また、そもそもとんちんかんなことを質問している場合、そのことをご指摘ください。

●質問者: xmisao
●カテゴリ:コンピュータ 科学・統計資料
○ 状態 :終了
└ 回答数 : 1/1件

▽最新の回答へ

1 ● sasada
●200ポイント

1. 文字列をキーとするインデックスで効率の良いハッシュというアルゴリズムがあり、一般的にRDBMSではそれを利用している。

ハッシュ関数 - Wikipedia

アルゴリズムとしては、MD5とかが有名です。

http://ja.wikipedia.org/wiki/MD5


xmisaoさんのコメント
キーは探索する値と大小を比較できる必要がありますから、元の値の大小関係を保持できないハッシュは利用できないのではないでしょうか。ハッシュをどのように利用してRDBMSがこの問題を問題を解決しているのかもう少し詳しくご教示願えませんか。

sasadaさんのコメント
ハッシュ値を使うのは全値一致の時のみです。というこで、こちらで必要なのは、ただのB・treeした。B+treeを使うからには、シーケンスな大小関係を扱うと言うことですね。失礼しました。 B+treeの方は、全文検索をベースにtreeを作るんですよ。力業ですね。各ノードのキーは全文が入っているリーフそのものだったりします。私が習ってる頃はそうでしたね。

xmisaoさんのコメント
確かに完全一致の場合にはハッシュが利用できますね。sasadaさんの見解はわかりました。回答ありがとうございました。
関連質問

●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ