データベースインデックスに関する世界観です。RDBMSの世界観も参照のこと。
データベースの探索性能を考える上で、「完全一致」と「部分一致」を区別することは重要です。
完全一致とは、検索文字列とどこかにあるその値が完全に一致することであり、部分一致とは完全には一致せず、一部分だけが一致することです。
完全一致（イコール検索）の場合、検索は一瞬でできます。なぜなら、その検索文字列から「ハッシュ値」を取って、そのハッシュ値をキーとする値にダイレクトにアクセスすればいいからです。
たとえば、「りんご」という値を探すとして、リストの中に「りんご」というキーを持つデータがあった場合、「りんご」というID情報でアクセスすれば、ほかのデータをわざわざ検索しなくても、一瞬で目的地にたどり着けます。
これは喩えるなら、WebサイトのURLが分かっているような場合だと言えます。URLさえ分かっていれば、何億というWebサイトがあるインターネットの中において、ほかのWebサイトの情報をわざわざ検索しなくても、一瞬でそのURLにたどり着けるのです。
部分一致の場合は、こうは行きません。たとえば、「りんご」を探そうとしても、キーには「果物」という情報しかない場合があります。この場合、果物というキーを持つデータの中から、ひとつひとつ目的のキー（すなわち果物の中のどれかが目的地）を探す必要があります（範囲検索）。
ですが、このようにひとつひとつ探索をかける場合であっても、二分探索木を使うことで、できるだけ素早く値を見つけることができます。
まず、あらかじめ、それぞれのキーの順序関係、すなわちアルファベット順に大きいあるいは小さいという関係を、ツリー構造として構築しておきます。
ツリーは親要素の下に右と左の子要素を持ち、右に行けば今よりも大きい値、左に行けば今よりも小さい値があります。すなわち、「これより右には現在地より大きい値しかない」「これより左には現在地より小さい値しかない」という風にツリーは整えらえています。
こうすることで、「こちらには値がある可能性はない」「値があるとしたらこちら」としてどちらに行くかを消め、行った先で「見つかった値からすると、こちらには値がある可能性はない」「あるとしたらこちら」と確認し、さらに探索を続けます。
結果、りんごが見つかる場合もあれば、りんごとなる値はひとつも見つからない場合もあります。
新しいキーを配置するためには、そのキーをどこに加えるべきかをまず探索によって探し出し、末端に辿り着いた状態で、親要素よりも大きければ右の子要素に、小さければ左の子要素とします。これにより、右にいけば必ず大きくなり、左にいけば必ず小さくなるよう、ツリーを常に探索可能な状態に維持しておきます。
このように、ハッシュ値で探索を一瞬で終わらせる場合と、二分探索木やそれに類するツリー構造でひとつひとつ探していく場合があります。ハッシュ値のデータ構造をハッシュテーブルと言います。また、二分探索木の改良版として、データベースではB-Treeという構造が使われます。
既出の単語を検索する時に、すべて総当たりで検索するのは時間がかかる。
このような時、二分木構造を用いた二分探索を行うことで、少ない手順で目的の単語に到達できる。
二分探索木を用いた探索では、より小さいものを左、より大きいものを右の子要素とする二分木を使う。全ての単語をこの規則にしたがって並べることで、最短で単語を検索できる。
AVL木は、木の高さが深くなりすぎないように、中心を回転させる平衡木のこと。
詳しくは「プログラミング言語C（K&R）」が参考になります。
B-Treeでは、木の高さが深くなりすぎないように平衡木が用いられている。
B-Treeでは、基本的にルートノードから、親ノードと子ノードを結合するブランチノードを辿り、リーフノード（データ本体へのポインタを持つ）を探す。
二分探索木と同様、探しているのよりも大きい値が見つかったかどうかで左と右のどちらの子ノードに進むかを振り分ける。探しているのより大きなポインタが見つかった場合は左の子ノードに、見つからなかった場合は右の子ノードに進む。これを繰り返してデータへと到達する（あるいはデータが存在しないことが分かる）。
また、カラムを指定してインデックスを作ることができる。カラムはひとつだけのカラムあるいは複数のカラムを指定できる。
詳しくは以下を参照してください。
自分の書いたブログ「未来のわたしの心より今のあなたへ」2021/03/27より。
ハッシュテーブルは、ハッシュ関数とハッシュ値によってキーと値の表で表されるデータ構造。
値が固定長になるため、検索効率が高く、どんなに値が増えても効率が変わらない。
内部の仕組みとしては、連結リストへのポインタを格納した配列を用いる。
すなわち、配列の要素がそれぞれの連結リストへのポインタとなる。
探索アルゴリズムにおいて、ハッシュテーブルはイコール検索に強いが、範囲検索は苦手。
これに対して、B-Treeはイコール検索も範囲検索もバランスよくこなす万能型。
（絵で見てわかるITインフラの仕組み (DB SELECTION)を参考に執筆しました。）
ハッシュテーブルは、キーのハッシュ値を要素の添え字とする配列によって実現できる。
（ハッシュテーブル (hash table)とは｜「分かりそう」で「分からない」でも「分かった」気になれるIT用語辞典を参考に執筆しました。）
MySQLでは、
CREATE INDEX インデックス名 ON テーブル名 (カラム名, ...);
でインデックスの作成、
DROP INDEX インデックス名 ON テーブル名;
でインデックスの削除を行えます。
詳しくは3ステップでしっかり学ぶ MySQL入門 (今すぐ使えるかんたんプラス)が参考になります。
データ構造やツリーや具体的なアルゴリズムを参照のこと。
Linuxカーネル開発（B-Treeファイルシステム）を参照のこと。