ランダムアクセス

質問

これまでの流れ
http://oshiete1.goo.ne.jp/qa3828256.html
http://oshiete1.goo.ne.jp/qa3829067.html

そして結局ランダムアクセスでやろうとゆうことになって問題が・・。

aaa
bcde
ddj
jk

これに cd を追加したいときランダムアクセスでは ddj と jk を
再配置しなければならない。（理由はゆうまでもなく2分検索を使うため）
これでは項目が増えると処理が重くなるのですがどうしたらいいですか？

回答No.2

noname#245945

こんにちは

先に解答を言いますと、
Q:これでは項目が増えると処理が重くなるのですがどうしたらいいですか？
A:宿命ですのであきらめてください。

速い、遅いは環境によって様々に言われるので一概に言えるものではありませんが、注意したいのは一般にデータベースソフトは直接ファイルアクセスした場合よりも遅いと言うことです。
また、キャッシュ付きの探索を行う場合、要素数が少なければ(～１万行ぐらいでしょうか)ランダムアクセスするよりもシーケンシャルにアクセスする方が速いのではないかと私は見積もります。
ですから、想定される要素数にもよりますが、まずはバカサーチするように実装して、プロファイリング時にボトルネックとなるようであればデータベースライブラリの導入を検討すればよいのではないでしょうか。

データベースの勉強をしていらっしゃって、実装を考えておられるのでしたら、ファイルベースのデータベースライブラリではBerkeleyDBやSQLiteのソースが公開されています。

回答No.1

auty

速く検索できる方法を考えるとき
　　　1.　検索対象をすでにソートされているものに限定するか。
　　　2.　データの管理（追加・修正・削除）を含んだ検索をする。
の2通りがあります。

2.の場合、
どの程度頻繁にデータの更新が行われるのか、
その更新のために、データを実際にソートしなおすの、
インデックスを作成してそれを利用するのか、そのの更新をどのように効率的に管理するのか、
といった問題を処理していくことになると思います。

これらのデータの管理を行うのが、まさにデータベースアプリケーションの役割で、
1.に限定せずに2.のことを行なおうとするとこういった問題が発生してくると思います。

お礼

char型１bytesなので正しくは
a～z,A～Zで５２文字(52bytes)、0～9で１０文字(10bytes)、
62bytes
long型のポインタとあわせても558bytes
それでも大きくなるような気がするのですがどうしたらいいですか？

補足

問題が発生してるから聞いてるのです。
Bツリーを使おうとして
っhttp://itpro.nikkeibp.co.jp/article/COLUMN/20060113/227239/
を見ながら、
この方法だと
a～z,A～Zで５２文字(8*52=416bytes)、0～9で１０文字(8*10=80bytes)、
次のノードへのポインタがlong型で62文字分(62*8=496bytes)
合計で992bytes

つまりこの方法でやろうとするとmoonとゆう単語をデータとして入力すると
m に992bytes, o に992bytes, o に992bytes, n に992bytes
約4Kbytes
２回目以降はappleを登録すると
a に0bytes, pple に4Kbytes
つまりあとに追加すればするほど容量を食わなくてすむのですが
この例のように単語２個で8Kbytesも使うとあとあと苦しいかと。
特にpneumonoultramicroscopicsilicovolcanoconiosisのような
長い単語をいれるとすぐにウンMBくらいいきそうです。

それと分からないのがリンク先にある
>一般的なページ・サイズとレコード数では，Bツリーの階層はせいぜい3～4階層にしかならないと考えていいでしょう。
のところ。普通に考えれば最初の説明のように入力単語そのものの
長さになる。