インデックスのアルゴリズムとBツリー

主キーじゃないカラムにインデックスを張るとき、
つまり、値が重複することがありうる場合に
利用されるBツリーは通常のBツリーと比較して、
どのように変更すればよいものでしょうか。

また、WHERE句内で * などを使用して検索するとき、
どのようにBツリー内を検索すれば効率的でしょうか。

データベースの実装に関する質問になりますが、
わかる方、よろしくお願いします。

No.1 ベストアンサー 回答者： taka_tetsu 回答日時： 2004/02/25 17:00

>利用されるBツリーは通常のBツリーと比較して、

>どのように変更すればよいものでしょうか。

末端においてテーブルの該当レコードのポインタを格納するのではなく、ポインタの集合が格納されている領域のポインタを格納しておく

>また、WHERE句内で * などを使用して検索するとき、
>どのようにBツリー内を検索すれば効率的でしょうか。

*ってワイルドカードのことですか？DBでは普通は%ですけど。

検索方法はbetweenと一緒でしょう。
あと、先頭にワイルドカードが指定されている場合はインデックスは使用しません。

こんなの見つかりましたけど。
http://www.hi-ho.ne.jp/tsumiki/doc_1.html

参考URL：http://www.hi-ho.ne.jp/tsumiki/doc_1.html

この回答へのお礼

回答ありがとうございます。

> ポインタの集合が格納されている領域のポインタを格納しておく

ここには一般的にどういうデータ構造が使用されるのですか？
リンクリストでしょうか。

> *ってワイルドカードのことですか？DBでは普通は%ですけど。

ワイルドカードです。バカなことを書いてしまいました。

between 指定したときの検索については
参考URLが非常に役に立ちました。
リーフ同士をリンクさせるのですね。。。


疑問点は大体消えました。
どうもありがとうございます。

お礼日時：2004/02/25 17:24

No.2 回答者： taka_tetsu 回答日時： 2004/02/25 19:13

>ここには一般的にどういうデータ構造が使用されるのですか？

>リンクリストでしょうか。

すべての重複項目をリンクリストで作るよりは、ある程度の領域を取ってまとめて格納し、あふれた分は別の領域へのリンクでしょうね、おそらく。

この回答へのお礼

なるほど。。
色々勉強になりました。
ありがとうございます。

お礼日時：2004/02/26 22:19