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


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

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

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

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

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

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

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

回答の条件
  • 1人5回まで
  • 13歳以上
  • 登録:2014/08/05 19:45:36
  • 終了:2014/08/12 19:50:06

回答(1件)

id:sasada No.1

sasada回答回数1482ベストアンサー獲得回数1332014/08/06 09:26:46

ポイント200pt

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

ハッシュ関数 - Wikipedia

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

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

他1件のコメントを見る
id:sasada

 ハッシュ値を使うのは全値一致の時のみです。というこで、こちらで必要なのは、ただのB・treeした。B+treeを使うからには、シーケンスな大小関係を扱うと言うことですね。失礼しました。

 B+treeの方は、全文検索をベースにtreeを作るんですよ。力業ですね。各ノードのキーは全文が入っているリーフそのものだったりします。私が習ってる頃はそうでしたね。

2014/08/06 21:01:29
id:xmisao

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

2014/08/06 21:55:24

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません