(2005.11更新)
データの検索の為のデータ構造とアルゴリズム：
以下でインデックス処理のために、データベース内部で利用されているデータ処理アルゴリズムについて説明する。
データの検索を効率的に行う為に、データの格納方法を工夫する。
そこで、データを記録するときには規則的に記録すれことにする。
データを記録するための規則をデータ構造と呼ぶ。
代表的なデータ構造：
２分木にデータを記録するときの規則：
２分木の検索手順：
２分木の問題点：
２分木について確認する：
2分木の規則に従って以下の木にデータを追加する。その後、検索の効率について検討する。
節の値を元に戻すには、ブラウザの「戻る」で戻って、再び「解説ページ」をクリックする。
検索の効率について：
上の例の様に、でたらめに並んだ１３個のデータからあるデータを見つける際には、平均６〜７回データを取り出して調べる必要があるが、上の例では、最悪でも４回の調査で目的のデータがあるかどうかを確認できる。
また、データがあらかじめ順番に並んでいる場合は、順位が中央の値と比較し、その大小関係で次に検索すべき範囲を決め、同様に新たな範囲の中央の値と比較してて行くことで、データを検索することが出来る。
これは、２分探索法と呼ばれるデータ探索のアルゴリズムである。
データを並べ替えることをソートといい、さまざまな手法が開発されている。
以下のものが有名、
ソートの練習（挿入ソート・バブルソート）
下の図では、コンピュータのメモリ上にデータが格納されているものとし、メモリ上の各データは一度に2個だけ値を参照して、大小関係を比べることが出来るものとする。
比較した2個のメモリの値を必要があれば入れ替えることで、データ全体を最終的に並べ替えることを目標として、下の図の「隣接データを交換」ボタンを押す手順を考えてみよ。
元に戻すには、ブラウザの「戻る」で戻って、再び「解説ページ」をクリックする。
■挿入ソート：
| 比較対象 | 交換有無 | 並べ替え完了範囲 |
| 1 2 | なし | 1 - 2 |
| 2 3 | なし | 1 - 3 |
| 3 4 | あり | |
| 2 3 | あり | |
| 1 2 | なし | 1 - 4 |
| 4 5 | あり | |
| 3 4 | あり | |
| 2 3 | あり | |
| 1 2 | あり | 1 - 5 |
| 以下略 |
■バブルソート：
| 比較対象 | 交換有無 | 並べ替え完了範囲 | 比較対象 | 交換有無 | 並べ替え完了範囲 | |
| 1 2 | なし | 1 2 | なし | |||
| 2 3 | なし | 2 3 | あり | |||
| 3 4 | あり | 3 4 | なし | |||
| 4 5 | あり | 4 5 | あり | |||
| 5 6 | あり | 5 6 | あり | |||
| 6 7 | あり | 6 7 | あり | |||
| 7 8 | あり | 7 8 | あり | 8 - 10 | ||
| 8 9 | あり | 1 2 | あり | |||
| 9 10 | あり | 10 | 2 3 | なし | ||
| 1 2 | なし | 3 4 | あり | |||
| 2 3 | あり | 4 5 | なし | |||
| 3 4 | あり | 5 6 | あり | |||
| 4 5 | あり | 6 7 | あり | 7 - 10 | ||
| 5 6 | あり | 1 2 | なし | |||
| 6 7 | あり | 2 3 | あり | |||
| 7 8 | あり | 3 4 | なし | |||
| 8 9 | あり | 9 - 10 | 4 5 | あり | ||
| 右上に続く | 5 6 | あり | 6 - 10 以下略 |
実は、上記の挿入ソートもバブルソートも、並べ替えるデータのサイズをＮとすると、並べ替えに要する手間がＮ自乗の爆発的に増えるという点で、効率の悪い手法である。
他のソートアルゴリズムについては略（この図では説明不能）。データベースでは、マージソートなど、より高速で大量のデータ向きのアルゴリズムが利用される。