結論
mlocate を apt でインストールしましょう。
$ sudo apt install -y mlocate パッケージリストを読み込んでいます... 完了 依存関係ツリーを作成しています 状態情報を読み取っています... 完了 提案パッケージ: nocache 以下のパッケージが新たにインストールされます: mlocate アップグレード: 0 個、新規インストール: 1 個、削除: 0 個、保留: 0 個。 50.1 kB のアーカイブを取得する必要があります。 この操作後に追加で 258 kB のディスク容量が消費されます。 ... ... Initializing mlocate database; this may take some time...（ここでとても時間がかかります）
$ locate --version mlocate 0.26 Copyright (C) 2007 Red Hat, Inc. All rights reserved. このソフトウェアは GPL v.2 に基づいて提供されています。 このプログラムは法律が許す範囲で無保証で提供されます。
補足
- インストール時にインデックスを作成するため、結構な時間がかかります*1
- 毎日自動でインデックスを作成してくれるため、手動でインデックスを作成する必要はありません
参考
*1:僕の場合は 40分 かかりました
