ところで、Redis ってなんでしょうか。Redis とは、一種の KVS (キーバリューストア)です。じゃあ KVS ってなんでしょうか。KVS というのは、「キー」と「バリュー(値)」が紐づいた状態で保存してあるデータベースのことです。連想配列みたいなもんですね。KVS さんに対して、「"apple"っていうキーで"りんご"っていう値を保存しておいて」と頼めば、KVS さんはディスク(やメモリ)にそれを保存しておいてくれます。そのあと、KVS さんに対して「"apple"っていうキーの値ってなに？」って問い合わせれば、KVS さんはディスク(やメモリ)からデータを読み出して「"りんご"だよ〜」って教えてくれるわけですね。
Redisがこれだけブームになっている理由のひとつとして、オンメモリで動きつつディスクに書き出すっていうおもしろ機構(おもしろを狙ってるわけじゃなくて便利だからそうなってるんだけど)と、いろんなデータ型とそれに対する操作をネイティブでサポートしている、というのがあります。前者は、データ型と関係ないので今回は触れません。今回は、この「いろんなデータ型とそれに対する操作をネイティブでサポートしている」というところを題材にして、いろんなデータ型と、それに対する操作の計算量について見て行くとしましょう。