データベースのインデックス作成はどのように機能しますか?

2008年08月04日に質問されました。  ·  閲覧回数 890.1k回  ·  ソース

Xenph Yan picture
2008年08月04日

データセットのサイズが大きくなるにつれてインデックス作成が非常に重要になることを考えると、データベースに依存しないレベルでインデックス作成がどのように機能するかを誰かが説明できますか?

フィールドにインデックスを付けるクエリについては、データベース列にインデックスを付ける方法をご覧ください。

回答

Xenph Yan picture
2008年08月04日
3664

なぜそれが必要なのですか?

データがディスクベースのストレージデバイスに保存される場合、データのブロックとして保存されます。 これらのブロックは完全にアクセスされるため、アトミックディスクアクセス操作になります。 ディスクブロックは、リンクリストとほぼ同じ方法で構造化されています。 どちらにもデータのセクション、次のノード(またはブロック)の場所へのポインターが含まれており、両方を連続して格納する必要はありません。

多数のレコードは1つのフィールドでしか並べ替えることができないため、並べ替えられていないフィールドでの検索には、(平均で) N/2ブロックアクセスを必要とする線形検索が必要であると言えます。 Nは、テーブルがまたがるブロックの数です。 そのフィールドが非キーフィールドである場合(つまり、一意のエントリが含まれていない場合)、テーブルスペース全体をNブロックアクセスで検索する必要があります。

一方、ソートされたフィールドでは、 log2 Nブロックアクセスを持つバイナリ検索を使用できます。 また、データは非キーフィールドを指定してソートされるため、より高い値が見つかった後は、テーブルの残りの部分で重複する値を検索する必要はありません。 したがって、パフォーマンスが大幅に向上します。

インデックス作成とは何ですか?

インデックス作成は、複数のフィールドの多数のレコードを並べ替える方法です。 テーブルのフィールドにインデックスを作成すると、フィールド値と、それに関連するレコードへのポインタを保持する別のデータ構造が作成されます。 次に、このインデックス構造が並べ替えられ、バイナリ検索を実行できるようになります。

インデックス作成の欠点は、MyISAMエンジンを使用してインデックスがテーブルに一緒に格納されるため、これらのインデックスがディスク上に追加のスペースを必要とすることです。同じテーブル内の多くのフィールドにインデックスが付けられると、このファイルは基になるファイルシステムのサイズ制限にすぐに達する可能性があります。 。

それはどのように機能しますか?

まず、サンプルのデータベーステーブルスキーマの概要を説明しましょう。

フィールド名データ型ディスク上のサイズ
 id(主キー)符号なしINT4バイト
 firstName Char(50)50バイト
 lastName Char(50)50バイト
 emailAddress Char(100)100バイト

:ディスク値の正確なサイズを可能にするために、varcharの代わりにcharが使用されました。 このサンプルデータベースには500万行が含まれており、インデックスは作成されていません。 ここで、いくつかのクエリのパフォーマンスを分析します。 これらは、 id (ソートされたキーフィールド)を使用したクエリとfirstName (キー以外のソートされていないフィールド)を使用したクエリです。

例1-ソートされたフィールドとソートされていないフィールド

R = 204バイトのレコード長を与える固定サイズのr = 5,000,000レコードのサンプルデータベースが与えられ、それらはデフォルトのブロックサイズB = 1,024を使用しているMyISAMエンジンを使用してテーブルに格納されますbfr = (B/R) = 1024/204 = 5レコードになります。 テーブルを保持するために必要なブロックの総数はN = (r/bfr) = 5000000/5 = 1,000,000ブロックです。

idフィールドがキーフィールドである場合、idフィールドの線形検索では、値を見つけるために平均N/2 = 500,000ブロックアクセスが必要になります。 ただし、idフィールドもソートされているため、平均log2 1000000 = 19.93 = 20ブロックアクセスを必要とするバイナリ検索を実行できます。 これが劇的な改善であることがすぐにわかります。

現在、 firstNameフィールドはソートされておらず、キーフィールドでもないため、バイナリ検索は不可能であり、値は一意ではありません。したがって、テーブルは正確なN = 1,000,000ブロックアクセスを最後まで検索する必要があります。 インデックス作成が修正を目的としているのはこの状況です。

インデックスレコードにインデックス付きフィールドと元のレコードへのポインタのみが含まれていることを考えると、それが指すマルチフィールドレコードよりも小さくなるのは当然のことです。 したがって、インデックス自体に必要なディスクブロックは元のテーブルよりも少なく、したがって、反復処理に必要なブロックアクセスは少なくなります。 firstNameフィールドのインデックスのスキーマの概要を以下に示します。

フィールド名データ型ディスク上のサイズ
 firstName Char(50)50バイト
 (レコードポインタ)特別な4バイト

:MySQLのポインターの長さは、テーブルのサイズに応じて2、3、4、または5バイトです。

例2-インデックス作成

インデックスレコード長がR = 54バイトでデフォルトのブロックサイズB = 1,024バイトを使用するr = 5,000,000レコードのサンプルデータベースがあるとします。 インデックスのブロック係数は、ディスクブロックあたりbfr = (B/R) = 1024/54 = 18レコードになります。 インデックスを保持するために必要なブロックの総数はN = (r/bfr) = 5000000/18 = 277,778ブロックです。

これで、 firstNameフィールドを使用した検索で、インデックスを利用してパフォーマンスを向上させることができます。 これにより、平均log2 277778 = 18.08 = 19ブロックアクセスでインデックスのバイナリ検索が可能になります。 実際のレコードのアドレスを見つけるには、読み取りにさらにブロックアクセスが必要で、合計が19 + 1 = 20ブロックアクセスになります。これは、インデックス付けされていないfirstNameの一致を見つけるために必要な1,000,000ブロックアクセスとはかけ離れています。テーブル。

いつ使用する必要がありますか?

インデックスの作成には追加のディスクスペースが必要であり(上記の例から277,778ブロック余分に、最大28%増加)、インデックスが多すぎるとファイルシステムのサイズ制限から問題が発生する可能性があるため、正しいものを選択するには慎重に検討する必要があります。インデックスを作成するフィールド。

インデックスはレコード内の一致するフィールドの検索を高速化するためにのみ使用されるため、出力にのみ使用されるインデックスフィールドは、挿入または削除操作を実行するときにディスク領域と処理時間を無駄にするだけであるのは当然です。避けるべきです。 また、二分探索の性質を考えると、データのカーディナリティまたは一意性が重要です。 カーディナリティが2のフィールドでインデックスを作成すると、データが半分に分割されますが、カーディナリティが1,000の場合、約1,000レコードが返されます。 このようにカーディナリティが低いと、有効性は線形ソートに低下し、カーディナリティがレコード数の30%未満の場合、クエリオプティマイザはインデックスの使用を回避し、インデックスを事実上スペースの浪費にします。

Sankarganesh Eswaran picture
2017年04月23日
359

古典的な例「本の索引」

10章で分割された1000ページの「本」を考えてみましょう。各セクションは100ページです。

簡単ですね

ここで、「錬金術師」という単語を含む特定の章を見つけたいと想像してください。 索引ページがなければ、本/章全体をスキャンする以外に選択肢はありません。 すなわち:1000ページ。

このアナロジーは、データベースの世界では「全表スキャン」として知られています。

enter image description here

しかし、インデックスページがあれば、どこに行けばよいかわかります。 さらに、重要な特定の章を検索するには、インデックスページを何度も何度も確認する必要があります。 一致するインデックスを見つけたら、残りをスキップしてその章に効率的にジャンプできます。

ただし、実際の1000ページに加えて、インデックスを表示するにはさらに10ページが必要になるため、合計で1010ページになります。

したがって、インデックスは、効率的なルックアップのために、インデックス付きの列の値+インデックス付きの行へのポインタをソートされた順序で格納する別個のセクションです。

学校では物事は簡単ですよね? :P

Der U picture
2013年04月30日
248

初めて読んだときはとても助かりました。 ありがとうございました。

それ以来、インデックス作成の欠点についていくつかの洞察を得ました。1つのインデックスを使用してテーブル( UPDATEまたはINSERT )に書き込む場合、ファイルシステムには実際には2つの書き込み操作があります。 1つはテーブルデータ用で、もう1つはインデックスデータ用です(およびその再ソート(およびクラスター化されている場合はテーブルデータの再ソート))。 テーブルとインデックスが同じハードディスク上にある場合、これにはより多くの時間がかかります。 したがって、インデックス(ヒープ)のないテーブルを使用すると、書き込み操作を高速化できます。 (2つのインデックスがある場合、3つの書き込み操作などになります)

ただし、インデックスデータとテーブルデータ用に2つの異なるハードディスク上に2つの異なる場所を定義すると、時間のコストが増加するという問題を軽減/排除できます。 これには、必要なハードディスク上のファイルに応じた追加のファイルグループの定義と、必要に応じたテーブル/インデックスの場所の定義が必要です。

インデックスに関するもう1つの問題は、データが挿入される際の時間の経過に伴う断片化です。 REORGANIZE役立ちます。それを実行するには、ルーチンを作成する必要があります。

特定のシナリオでは、ヒープはインデックス付きのテーブルよりも役立ちます。

例:-競合する書き込みがたくさんあるが、レポートのために営業時間外に毎晩1回だけ読んでいる場合。

また、クラスター化インデックスと非クラスター化インデックスの区別はかなり重要です。

助けてくれました:-クラスター化インデックスと非クラスター化インデックスは実際にはどういう意味ですか?

hcarreras picture
2014年02月20日
245

インデックスは、データベース内の特定の列の検索を高速化する単なるデータ構造です。 この構造は通常、Bツリーまたはハッシュテーブルですが、他の論理構造にすることもできます。

Somnath Muluk picture
2016年08月14日
176

ここで、クエリを実行して、「Abc」という名前の従業員のすべての詳細を検索するとしますか?

SELECT * FROM Employee 
WHERE Employee_Name = 'Abc'

インデックスがないとどうなりますか?

データベースソフトウェアは、文字通りEmployeeテーブルのすべての行を調べて、その行のEmployee_Nameが「Abc」であるかどうかを確認する必要があります。 我々はその中に名前「ABC」ですべての行をしたいので、我々は名前「ABC」でただ一つの行を見つけたら、名前をABCで他の行があるかもしれませんのでそして、私たちは、探して停止することはできません。 したがって、最後の行までのすべての行を検索する必要があります。つまり、このシナリオの数千の行をデータベースで調べて、「Abc」という名前の行を見つける必要があります。 これは、いわゆる全表スキャンです。

データベースインデックスがパフォーマンスにどのように役立つか

インデックスを持つことの全体的なポイントは、調査する必要のあるテーブル内のレコード/行の数を本質的に削減することにより、検索クエリを高速化することです。 インデックスは、テーブル内の特定の列の値を格納するデータ構造(最も一般的にはBツリー)です。

Bツリーインデックスはどのように機能しますか?

Bツリーがインデックスの最も一般的なデータ構造である理由は、ルックアップ、削除、および挿入がすべて対数時間で実行できるため、時間効率が高いという事実によるものです。 また、Bツリーがより一般的に使用されるもう1つの主な理由は、Bツリー内に格納されているデータを並べ替えることができるためです。 RDBMSは通常、インデックスに実際に使用されるデータ構造を決定します。 ただし、特定のRDBMSを使用する一部のシナリオでは、インデックス自体を作成するときにデータベースで使用するデータ構造を実際に指定できます。

ハッシュテーブルインデックスはどのように機能しますか?

ハッシュインデックスが使用される理由は、値を検索するだけの場合、ハッシュテーブルが非常に効率的であるためです。 したがって、文字列と等しいかどうかを比較するクエリは、ハッシュインデックスを使用すると、値を非常に高速に取得できます。

たとえば、前に説明したクエリは、Employee_Name列に作成されたハッシュインデックスの恩恵を受ける可能性があります。 ハッシュインデックスが機能する方法は、列の値がハッシュテーブルへのキーになり、そのキーにマップされた実際の値がテーブルの行データへのポインタになることです。 ハッシュテーブルは基本的に連想配列であるため、一般的なエントリは「Abc => 0x28939」のようになります。ここで、0x28939は、Abcがメモリに格納されているテーブル行への参照です。 ハッシュテーブルインデックスで「Abc」のような値を検索し、メモリ内の行への参照を取得する方が、テーブルをスキャンしてEmployee_Name列で「Abc」の値を持つすべての行を見つけるよりも明らかに高速です。

ハッシュインデックスの欠点

ハッシュテーブルはソートされたデータ構造ではなく、ハッシュインデックスでも役に立たないクエリの種類がたくさんあります。 たとえば、40歳未満のすべての従業員を調べたいとします。 ハッシュテーブルインデックスでそれをどのように行うことができますか? ハッシュテーブルはキーと値のペアの検索にのみ適しているため、それは不可能です。つまり、同等性をチェックするクエリを意味します

データベースインデックスの内部には正確には何がありますか? これで、データベースインデックスがテーブルの列に作成され、インデックスがその特定の列に値を格納することがわかりました。 ただし、データベースインデックスは、同じテーブルの他の列に値を格納しないことを理解することが重要です。 たとえば、Employee_Name列にインデックスを作成する場合、これは、Employee_Age列とEmployee_Address列の値もインデックスに格納されないことを意味します。 他のすべての列をインデックスに格納しただけの場合は、テーブル全体の別のコピーを作成するのと同じようになります。これは、スペースを取りすぎて非常に非効率的です。

データベースは、インデックスをいつ使用するかをどのように知るのですか? 「SELECT * FROM Employee WHERE Employee_Name = 'Abc'」のようなクエリが実行されると、データベースはクエリ対象の列にインデックスがあるかどうかを確認します。 Employee_Name列にインデックスが作成されていると仮定すると、データベースは、検索対象の値を見つけるためにインデックスを使用することが実際に意味があるかどうかを判断する必要があります。データベースインデックスを使用する方が実際には効率が悪いシナリオがあるためです。 、およびテーブル全体をスキャンするだけでより効率的です。

データベースインデックスを持つためのコストはいくらですか?

スペースを占有します。テーブルが大きいほど、インデックスも大きくなります。 インデックスでパフォーマンスが低下するもう1つの点は、対応するテーブルの行を追加、削除、または更新するたびに、インデックスに対して同じ操作を実行する必要があるという事実です。 インデックスには、インデックスがカバーするテーブル列にあるものと同じ分までのデータが含まれている必要があることに注意してください。

原則として、インデックス付きの列のデータが頻繁にクエリされる場合にのみ、インデックスをテーブルに作成する必要があります。

も参照してください

  1. 一般的にどの列が適切なインデックスになりますか?
  2. データベースインデックスはどのように機能しますか
ProgrammerPanda picture
2016年08月02日
108

簡単な説明!

インデックスは、テーブル内の特定の列の値を格納するデータ構造に他なりません。 テーブルの列にインデックスが作成されます。

例: Userというデータベーステーブルがあり、 NameAgeAddress 3つの列があります。 Userテーブルに数千の行があると仮定します。

ここで、クエリを実行して、「John」という名前のユーザーのすべての詳細を検索するとします。 次のクエリを実行すると、次のようになります。

SELECT * FROM User 
WHERE Name = 'John'

データベースソフトウェアは、文字通りUserテーブルのすべての行を調べて、その行のNameが「John」であるかどうかを確認する必要があります。 これには長い時間がかかります。

ここでindex役立ちます。インデックスは、調査が必要なテーブル内のレコード/行の数を本質的に削減することにより、検索クエリを高速化するために使用されます。

インデックスの作成方法:

CREATE INDEX name_index
ON User (Name)

indexは、 1つのテーブル構成され、それらの値はます

インデックスはおそらくユーザー名のアルファベット順にソートされるため、データベースはインデックスを使用してJohnという名前の従業員を検索します。 また、並べ替えられているため、「J」で始まるすべての名前がインデックス内で隣り合っているため、名前の検索がはるかに高速になります。

Raza picture
2015年01月14日
36

簡単な提案です。インデックス作成には追加の書き込みとストレージスペースが必要になるため、アプリケーションでより多くの挿入/更新操作が必要な場合は、インデックスなしのテーブルを使用することをお勧めしますが、より多くのデータ取得操作が必要な場合は、インデックス作成を行う必要があります。テーブル。

Alf Moh picture
2016年12月22日
32

データベースインデックスを本のインデックスと考えてください。

犬に関する本を持っていて、たとえばジャーマンシェパードに関する情報を見つけたい場合は、もちろん本のすべてのページをめくって探しているものを見つけることができますが、これはもちろん時間がかかり、そうではありませんとても早い。

もう1つのオプションは、本の[インデックス]セクションに移動し、探しているエンティティ(この例ではジャーマンシェパード)の名前を使用して探しているものを見つけ、ページ番号を確認することです。探しているものをすばやく見つけます。

データベースでは、ページ番号は、エンティティが配置されているディスク上のアドレスにデータベースを転送するポインタと呼ばれます。 同じジャーマンシェパードのアナロジーを使用すると、次のようなもの(「ジャーマンシェパード」、0x77129)が得られます。ここで、 0x77129は、ジャーマンシェパードの行データが格納されているディスク上のアドレスです。

つまり、インデックスは、クエリ検索を高速化するために、テーブル内の特定の列の値を格納するデータ構造です。