я далеко не спец в (key-value) бд, но например тот же редис пише что GET <key> выполнется за O(1) поэтому и спрашиваю, типа есть ли смысл писать key-value бд в которой чтение и запись не за O(1) ?
key-value разные бывают, какие-то чисто для чтения, какие-то для записи O(1) дают, но у каждого из этих способов есть свои минусы, нельзя сделать и чтение и запись за O(1). В redis не разбирался что внутри, но O(1) это хеш индексы, типа как md5 (очень грубо говоря), но более навороченные, и нужно смотреть, что они там с коллизиями делают, там или вариант перезаписать старые данные при добавлении или хранить все значения, но и тот и тот вариант имеют свои минусы)) В общем не получится у вас читать и записывать за O(1) темболее в диск))