DBエンジンの仕組みについて

質問

はじめして。
例えば、認証システムを作ろうとします。
現在一万人の登録があるとして、田中さんが8千人目に登録されているとします。
そして、田中さんを検索するとき、
PerlとCSV形式のテキストファイル使用して検索する場合、上から順に8千行まで探して見つけますよね。
MySQLなどのDBサーバーを仕様する場合は、どういう形式で保存されているて、どういう形で検索するのでしょうか？
DBエンジンを使うと何万件もの登録に耐えれ、かつレスポンスも早いとききます。なぜそうなのか、その根本的な仕組みをどなたか教えていただけないでしょうか？

回答No.3

MarrowG · ベストアンサー

ＤＢエンジンでも索引無しの場合は全データを上から順に検索していきます。
索引無し検索の場合、検索速度は大変遅くなります。
数千～数万件程度では索引無しでもそれほど大きな違いは出ませんが、数千万件のデータがあるような場合は必ず索引を付けなければ実用に耐えません。

ＤＢエンジンによっては、ＯＳが提供するファイルシステムを使用しないものもあります。
ＤＢエンジンが独自にＩ／Ｏを行うことによってＯＳのオーバーヘッドを避け、より高速なＩ／Ｏを実現するためです。
これを使うと、ファイルシステム上のデータを検索するより遥かに高速にデータを取り出すことが出来ます。

またＤＢエンジンの設定にもよりますが、メモリ上に読みこむのは通常は索引だけです。
一旦読みこんだ実データ（レコード）はメモリ上にキャッシュされますが、使用されなけばキャッシュからは順次破棄されていきます。
でも出来るだけキャッシュをたくさん取れる様にしておいた方がパフォーマンスは良くなります。（当たり前ですね（＾＾；）

＞例えば、一万件のレコードをもつファイルが一つあるとします。
＞ そして欲しいレコードが五千件目とわかっているとします。

ＤＢエンジンにも依りますが、一般的なＤＢエンジンなら５０００件目という概念はほとんど意味がありません。
索引が無ければ全件を検索しにいきますし、索引があれば検索条件にヒットしたレコードだけが選択されるからです。
索引付きのデータの場合、メモリに読みこまれる（＝ディスクから読みこむ）のは検索条件にヒットしたデータだけです。

また通常ＤＢで使用されるテーブルは固定長レコードです。（各カラム毎にフィールド長が決まっています）
CSVのように可変長レコードではありません。
可変長フィールドを扱う場合、可変長フィールドには実際のデータを保持しているファイル等へのポインタしかありません。
このため、可変長フィールドがあっても実レコード長はほぼ固定です。

データが固定長であるため、CSVのように行末文字の検索をする必要がなく、より高速なＩ／Ｏが可能になります。
特に索引付きである場合、該当レコードはこのファイルの先頭から何バイト目というように直接読み出すことが可能になるわけです。

その他、ＳＱＬで複雑な検索ができたりなど、ＤＢエンジンを使用するメリットは多く、業務アプリケーションには必須といえる存在です。

補足

みなさん。回答ありがとうございます。本当にためになります。最後に私の解釈を確認したいのです。

「索引は、HD上のアドレスを保持しているため、特定のレコードだけ読み込む事が出来る。索引をつけない場合、HDのアドレスを特定できないため、ファイルが、バイナリであろうと、ｃｓｖ（テキスト）であろうと、その欲しいレコードまですべて読み込まなければ特定できない。例えば五千件目に記録されてる場合、五千件目のレコードだけほしくても五千件目までのデータすべて読み込むことになってしまう。」

という解釈でよろしいでしょうか？

回答No.2

yuji

DBエンジンでデータを取り出す場合には
おそらく二分木探索（バイナリサーチ）が使用されているものだと思います。
例えば７つのデータがあった場合に
下記のような構造でデータを管理しているのでしょう。
（論理的に、ですが）

　　　４
　３　　　６
１　２　５　７

ここで５番目の値を取り出したい場合は
一番上の４と比較して、それより５が大きいので右下に進みます。
その後、６と比較してそれより５が小さいので左下に進みます。
その後、５と比較してそれと一致するのでそこのデータが
目的のデータとなるわけです。
７つの場合ですが、必ず３回以内の比較で目的のデータ
へたどり着くことができます。

１，２，３，４，５，６，７
と並べて順に探索していく場合だと最悪７回比較する
必要があります。

これはデータ数が多ければ多いほど、その差が大きく
なっていきます。

補足

ありがとうございます。参考になります。
補足で教えて下さい。

１、あるテーブルでどのフィールドにもIndex(索引)＝バイナリサーチをつけない場合は、DBエンジンの探し方も、保存形式がバイナリかテキスト化の違いだけで、Perl+ｃｓｖと同じ上から順に目的のレコードに到達するということですよね？

２、これは、パソコンの基本的動作の質問にはいると思うのですが、
例えば、一万件のレコードをもつファイルが一つあるとします。
そして欲しいレコードが五千件目とわかっているとします。
この場合メモリにバイナリデータでもテキストデータでも一万件のデータ＝一つのファイルをすべて読み込んでから上から順に五千件目に到達するのでしょうか？私はプログラム、テキストベースの考え方しか出来ないので、そのファイルを扱う場合、いったんメモリにそのファイルのすべてを読み込むというイメージがわきます。
それとも、その部分だけメモリに読み込むことがバイナリデータの場合可能なのでしょうか？
私の勝手な今の偏見なのですが、可能じゃないとIndexの意味がないと思ってしまうのですが。

回答No.1

X-Terra

勿論、圧縮技術なども速さの要因にはなりますが、根本的な理由として、以下が挙げられます。
Perl+CSVの場合、上から順に、ファイルの一行一行をすべてプログラム内で読み込み処理します。データベースシステムの場合は、「索引情報」というものを用いて、直接ファイルを読み込まずに、索引情報を参照し該当したもののポインタやリンク情報を基にデータを吐き出します。
索引には、「田中さんはどこにいるか」という、「番地番号（何行目）」も入っていますので、それを基にデータを読み込む、というわけです。

このような手法は、コンピューターが一般的に（ファイルを読み込むときなどに）行う手法でもあります。デフラグというのは、番地が飛び飛びになったものを順序良く戻す、ということですが、索引を付け直す、というのと同じことをやっているといえましょう。

補足

回答ありがとうございます。補足質問させて下さい。
１、索引を使用しない場合、レスポンスの差は圧縮技術の差によるとういこでしょうか？MySQLなどでDBのバックアップをとるとテキストとしてはきだされますが、それはバックパップ用で実際はバイナリとして保存されているということでしょうか？

２、索引を利用するとき、一万件のデータをいったメモリ上に読み込ムわけですよね？その場合ｃｓｖで順に読み込むとのレスポンスの違いが明確にわかりません。

詳しく教えていただけないでしょうか？よろしくお願いします。