TL;DR

初心者向け
適切な探索方法を選んで、実行時間を短くする方法を学びましょう
単純な処理でも20億回実行したら0.5秒ぐらいかかります
- （なおDB接続を繰り返すと桁外れに時間がかかります）

主要な探索の種類とイメージ

線形探索
二分探索
ハッシュ探索

mail_addressを指定してcustomerを検索する例を考えてみましょう

線形探索

対象データを順番に参照して、検索キーmail_addressが一致しているか調べます

計算量

1024件のデータがあれば1024回参照します。愚直。

O(n)

二分探索

mail_addressで全体をソートします
真ん中辺りのデータを参照して、一致しているか調べます
一致していなければ半分を捨てて、残りの半分の真ん中を参照します
一種の分割統治法

計算量

1024件 = 2^10件 = 222222222*2件を半分ずつ捨てながら見るので、
最大でも10個のデータを参照すれば見つかります。賢い。

O(\log n)

※計算機科学で言うlogの底は2です。 2^(log n) = n です

ハッシュ法

計算量

1024件でもハッシュ関数を1度経由すれば、対象データを直接参照できます

O(1)

欠点

一般的に、アルゴリズムは実行時間短縮とメモリ消費低減のトレードオフです
両方が悪い実装は存在しますし、作れますが、
それぞれで同時に最高のパフォーマンスを出すアルゴリズムは存在しないでしょう
ハッシュ法もご多分に漏れず、メモリを食います

データベースで使われているのは？

PostgreSQL 実行計画(explain, explain analyze)

Seq Scan: 線形探索
Index Scan: 二分探索っぽいもの
Hash ~: ハッシュ法

PostgreSQL Index Only Scan 奮闘記その3 | TECHSCORE BLOG
【SQL】ゼロ知識から実行計画を読み解きパフォーマンス改善 - Qiita
EXPLAIN - PostgreSQL 10.5文書

Java実装・計測

探索の実装前に

単純な処理分岐でも20億回実行したら0.61秒かかります

ベースにするソースコード

100000人のcustomerを用意して、メールアドレスを1000回検索してみましょう。
https://ideone.com/w0hDzg

検索処理を入れる場所(TODO)が未実装の状態で0.9秒です。

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// n人分のデータを作り
		int n = 100000;
		Random rand = new Random();
		String[][] customer = new String[n][2];
		for (int i = 0; i < n; i++)
			customer[i][0] = String.valueOf((char) (rand.nextInt(26)+'a')) + i + "@ab.com";
		for (int i = 0; i < n; i++)
			customer[i][1] = i + "さん";
 
		// メールアドレスでソートします
		Arrays.sort(customer, (c1, c2) -> c1[0].compareTo(c2[0]));
 
		// キーをメールアドレス、値を名前としたハッシュマップも作ります
		Map<String, String> hashmap = new HashMap<>(n);
		for (String[] c : customer)
			hashmap.put(c[0], c[1]);
 
		// 同じcustomer(101番目)の名前が取れる
		System.out.println(customer[101][0] + "の名前は" + customer[101][1]);
		// ハッシュマップからメールアドレスで取ることもできる
		System.out.println(customer[101][0] + "の名前は" + hashmap.get(customer[101][0]));
		System.out.println("確認終わり");
 
		// では、m人分のメールアドレスを適当に選んで
		int m = 1000;
		String[] keys = new String[m];
		for (int j = 0; j < m; j++)
			keys[j] = customer[rand.nextInt(n)][0];
 
		// １人ずつ
		for (int j = 0; j < m; j++){
			String key = keys[j];
			// 検索してみましょう
 
			// TODO
			String found = null;
 
			if (j % 100 == 0) {
				System.out.println(key + "の名前は" + Objects.toString(found, "不明"));
			}
		}
	}
}

線形探索

3.9秒です。遅い！
https://ideone.com/GIle7V

// TODOだった場所
String found = null;
for (int i = 0; i < n; i++) {
    if (Objects.equals(key, customer[i][0])) {
        found = customer[i][1];
    }
}

二分探索

1秒です。そもそもデータ用意が0.9秒だったので、検索自体にほとんど時間がかかっていません
https://ideone.com/eF7Txv

// TODOだった場所
String found = null;
keyCustomer[0] = key;
int index = Arrays.binarySearch(customer, keyCustomer, (c1, c2) -> c1[0].compareTo(c2[0]));
found = customer[index][1];

ハッシュ法

0.93秒です。ほぼ全く時間がかかりません
https://ideone.com/67PzQP

// TODOだった場所
String found = null;
found = hashmap.get(key);

二分探索(1024倍)

二分探索とハッシュ法の差が誤差レベルだったので、
検索回数(m)を1024倍にして比較してみましょう。
二分探索は1.69秒です。
https://ideone.com/ppG31d

ハッシュ法(1024倍)

ハッシュ法の検索回数(m)も1024倍にしてみましょう。
1.16秒です。
https://ideone.com/ppG31d
二分探索よりも、検索キーの増加に対して実行時間の伸びが緩やか。計算量の差です

探索って実際に開発で使うの？

　初学者が意識する機会は少ないでしょうが、利用しています。
　データベースで注文履歴一覧を検索する状況を考えてみましょう。SQLでcustomer顧客テーブル(1万件超)にorder注文テーブル(1万件超)とorder_detail注文明細テーブル(1万件超)を結合して明細を取得して、さらにproduct商品テーブル(1万件超)を結合して商品名を取得します。
　あなたがこのSQLを実行して現実的な時間で終了するのであれば、DB管理者が適切な主キー制約／一意制約／インデックスなどを設定して、DBがそれに基づいて二分探索（っぽいもの）に使う木構造データやハッシュ法に使うハッシュ表を事前に用意して、SQL実行時に利用されているのでしょう。
　なお現場では、DB定義が抜けているために処理が遅い／SQLのテーブル結合条件が複雑なため線形探索しかできず、遅い／本番環境で動かすまでそれらの問題に気づかない／改善余地はあるが放置される、といった不幸な状況が多く発生します。
　あなたの担当の外にも疑わしい箇所がある、ということは知っておいてください。

Hope this helps.

その他、参考

[線形探索（リニアサーチ）とは - IT用語辞典 e-Words]
(http://e-words.jp/w/%E7%B7%9A%E5%BD%A2%E6%8E%A2%E7%B4%A2.html)
二分探索（2分探索）とは - IT用語辞典 e-Words
ハッシュ法（ハッシュ探索）とは - IT用語辞典 e-Words
線型探索 - Wikipedia
二分探索 - Wikipedia