indexedDB、localStorageと連想配列で、部分一致検索のスピードは？

# indexedDB、localStorageと連想配列で、部分一致検索のスピードは？

## はじめに
連想配列はプログラムの中で、localStorageはブラウザの中で利用できるweb storageで、共にキーからバリューを求めることができます。
indexedDBは、多彩なweb storageで、オブジェクト、画像（blobデータ形式）などが保存できます。検索では、いろいろなキーを利用して、データを取得することができます。
これらは、いずれもキーが分かっていれば、高速に検索ができるweb storageです。
一方で、キーの一部しか分からないことはよくあります。このようなとき、高級なDBではLIKE検索で対応できます。今回のweb storageの中で、DBに近いindexedDBでも、LIKE検索機能はありません。
本稿では、キーも一部しか分からないとき、これらのarray、storageでは、どのようにして検索を行うか、またその時のパフォーマンスはどうであるか、について調べました。

## 利用するデータ
[駅データ.jp](https://ekidata.jp)（現時点の登録数10,936駅）を利用します。
このサイトは、都度メンテナンスされていて、廃線情報も含まれています。
採用したデータ列は、"station_cd, station_name, line_cd, pref_cd, post, address, lon, lat, close_ymd"です。
キーは、少し乱暴ですが、住所を用います。
なお、同じ住所もあるため、正確なキーは、”駅コード＋住所”としました。

## 方法
- キーの部分一致検索を行うためには、全キーを総なめします（この方法しか思いつきませんでした）。

- 部分一致検索で利用した文字は、”市”、”川”、”馬”、”郡”、”犬”、”上”、”新”、”大”、”下”、”山”の10文字です。
これら10文字を用いて、それぞれの文字で部分一致検索を10回行い、各処理の時間を測定しました。

- indexedDBの場合
キーが分からず1件1件取得できないため、indexedDBから丸毎データを取り出したデータで、部分一致検索を行いました。

- localStorageの場合
全キーの取得と同時にその値も取得してデータで、部分一致検索を行いました。

- 連想配列
全キーの取得し、そのキーで値を取得してデータで、部分一致検索を行いました。

## 実行結果
上記の10文字を用いて、それぞれ総なめで部分一致検索を行ったところ、10,936件中、平均ヒット数1,690件のヒットがあり、この時の検索処理スピードは、次の通りです。
　　　indexedDB	　　平均49.21ms、　最大56.20ms、最小36.50ms
　　　localStorage	　平均 6.12ms、　最大 7.60ms、　最小 4.80ms
　　　連想配列　　　平均 2.08ms、　最大 4.40ms、　最小 1.50ms
　　　　　MacBook Pro(14inch 2021)で計測

## まとめ
- 総なめ方式で部分一致検索の性能を見たところ、いずれのweb storageでも、十分なパフォーマンスを得ることができました。
- ローカルにデータを保存するindexedDBが思いの外、遅くないと結果が得られました。この処理速度は、インタラクティブな処理の範囲で十分な速さだと感じました。
- localStorageは、Googleはあまり非推奨していないそうですが、永続できる高速のストレージとして、利用したいと思いました。
- 連想配列は、比較のために掲載したものですが、大変便利な配列で、どんどん使って欲しいです。キーがあれば、配列をfor文で回さなくても、１発でデータがゲットできます。
- localStorag、indexedDBでデータの永続化を行う場合、パスワードなど機微な情報は、何らかの手段で、マスクする、暗号化することが必須となることに留意が必要です。

## 使用したプログラム
本稿では、駅データを読み込み、検索したい文字列を検索を行います。
[駅データ.jp](https://ekidata.jp)の路線データは、それぞれダウンロードしてください。
読み込んだcsvデータは[PapaParse](https://www.papaparse.com/)で、json化しています。

``` stations.html
<!DOCTYPE html>
<html lang="ja">
<head>
<meta charset="UTF-8">
<title>indexedDB、localStorageと連想配列</title>
<script src="https://unpkg.com/dexie@latest/dist/dexie.min.js""></script>
<script src="https://unpkg.com/papaparse@latest/papaparse.min.js"></script>
</head>

<body>
<input type="file" onchange="readFileStation(this)">
<br/>
<br/>
<label>地名：<input type="text" id="ekimei" size="40" value=""></label>
<input type="button" value="検索" id="kButton" onclick="kensaku()">
<pre id="preview1" ></pre>
<pre id="preview2" ></pre>
<pre id="preview3" ></pre>

<script>
let db = new Dexie('stations');
db.version(1).stores({
	stations: "station_cd,station_name,line_cd,pref_cd,post,address,lon,lat,close_ymd",
	lines: "line_cd,company_cd,line_name,line_name_k,line_name_h,line_color_c,line_color_t,line_type,lon,lat,zoom,e_status,e_sort"
});
db.stations.clear();
localStorage.clear();

let stationsA = [];//連想配列の全データ
let stationsI = [];//indexedDBの全データ
let stationsL = [];//localStorageの全データ

//駅データの読み込み
function readFileStation(input) {
	let file = input.files[0];
	let reader = new FileReader();
	reader.readAsText(file);
	reader.onload = function() {
		let d = reader.result;
		let lines = d.split('\n');
		let s = 'station_cd,station_name,line_cd,pref_cd,post,address,lon,lat,close_ymd\n';
		let = n = 0;
//路線データの内、データとして利用する部分だけ抽出
		for (let i = 0; i < lines.length; i++) {
			if (lines[i].charAt(0) == '#') continue;
			d = lines[i].split(',');
			if (stationsA[d[8]]) continue;//重複防止

//連想配列に格納
			stationsA[d[0] + d[8]] = '{"station_cd":' + d[0] + ', "station_name":' + d[2] + ',"line_cd":' + d[5] + ',"pref_cd":' + d[6] + ',"post":' + d[7] + ',"address":' + d[8] + ',"lon":' + d[9] + ',"lat":' + d[10] + ',"close_ymd":' + d[12] + '}';

//localStorageに格納
			localStorage.setItem('eki:' + d[0] + d[8], stationsA[d[0] + d[8]]);
			s += d[0] + ',' + d[2] + ',' + d[5] + ',' + d[6] + ',' + d[7] + ',' + d[8] + ',' + d[9] + ',' + d[10] + ',' + d[12] + '\n';
			n++;
		}
		document.querySelector('#preview1').textContent = 'data=' + n + '\n' + s;

//indexedDBに一括格納
		let data = Papa.parse(s, {header: true});//csvからjsonに変換
		db.stations.bulkAdd(data.data);

	};//end of reader.onload

	reader.onerror = function() {
console.log(reader.error);
	};
}

async function gets() { return await db.stations.toArray() }

//総なめ、部分一致検索
async function kensaku() {

//indexedDBから全件取得し、部分一致検索を行う ----------------------------------------------
let start = performance.now();
	stationsI = await gets();

	let ekimei = document.getElementById('ekimei');
	let eki = ekimei.value;

	let dt = '';
	let nn = 0;
	stationsI.forEach(async (station) => {
		if (station.address && station.address.indexOf(eki) >= 0) {//部分一致
			dt += JSON.stringify(station) + '\n';
			nn++;
		}
	});
	document.querySelector('#preview1').textContent = 'indexedDB=' + nn + '\n' + dt + '\n';
let end = performance.now();
console.log('indexedDB', eki, nn, (end - start));

//localStorageの全キーとその値を取得し、部分一致検索を行う ----------------------------------------------
start = performance.now();
	stationsL = Object.keys(localStorage).map(key => {
		return [
			key,
			localStorage.getItem(key)
		]
	});

	dt = '';
	nn = 0;
	for (let i in stationsL) {
		if (stationsL[i][0].indexOf(eki) >= 0) {//部分一致
			dt += stationsL[i][1] + '\n';
			nn++;
		}
	}
	document.querySelector('#preview2').textContent = 'localStorage=' + nn + '\n' + dt + '\n';
end = performance.now();
console.log('localStorage', eki, nn, (end - start));

//連想配列を総なめし、部分一致検索を行う ----------------------------------------------
start = performance.now();
	let keys = Object.keys(stationsA);
	dt = '';
	nn = 0;
	for (let k of keys) {
		if (k.indexOf(eki) >= 0) {//部分一致
			dt += stationsA[k] + '\n';
			nn++;
		}
	}
	document.querySelector('#preview3').textContent = '連想配列=' + nn + '\n' + dt + '\n';
end = performance.now();
console.log('連想配列', eki, nn, (end - start));

}//end of function kensaku
</script>

</body>
</html>
```