Хранение кеша PageRank - структура данных?

Да не, упаси господи. Если хранить тот же хеш, то получится те же 16 байт. varchar(16), понимаете. Это же строка.

Я бы не против был писать такое на пхп - фронтенд с каким нить опкод компилятором работал бы более чем приемлимо. Но эту мудню с кешем я бы не мутил. майскл и опционально нжинкс на фронте, да и еще и APC на крайняк с этой задачей справляется на отлично. К тому же забудьте про бинарные деревья. Б-деревья наше все. Учитывая, что в Б-дереве принципиально не будет много листьев, можно ограничить хеш байтами 8ю. Порядок я бы выбрал например 10. на 10 миллионах записей в худшем случае глубина будет 7 log 5(10) - это всего лишь 10, итого максимальное время поиска составит 20 шагов (без хеша, замечу), а среднее - 10 lg 10+10 =11. И на С хешем стало быть максимальное 11 а среднее 7. И расходы на него копеечные, ибо листьев наберется максимум миллион. Можно вообще за хеш-функцию взять 32-битный MD6 (48 раундов на вычисление конечно) или CRC32 =). В случае тупо бинарного дерева на 10 миллионах записей будет 23 уровня и даже при моментальном поиске хеш займет 10^7*16=160 мб, а не 4.

Косяк вашей теории только в том, что в пхп нет указателей. И даже при использовании боле-мене стабильной мемкаши мемлики гарантированы.

Если у кого нибудь найдется база на 10 миллионов записей с уникльным текстовым полем (tinytext) например, я готов продемонстрировать что правильная настройка майскла в пух и нжинкса в пух и прах изничтожит все танцы с мемкашед.

Я думаю он имел ввиду, что в связи с тем, что много записей с одним хостом, а уж тем более с .ru, у большой части записей начало этого ключа будет повторяться - засчет чего вся структура будет хорошо упаковываться и удачно индексироваться муськой например.

Для начала надо разделить хрениние и кеширование..это две разных задачи.

Хранить нужно в бд или на файлах. Учитывая что домен уникален - хеш не нужен.

Решение на БД - лишние движения на взаимодействие с БД, кеширование средствами БД либо дополнительный кеш на файлах, в memcached или еще как нибудь. Итого куча геморроя (сам себе злобный буратино).

Я бы сделал на файлах. Просто нужно нормальную файловую систему, без падения производительности на большом кол-ве файлов + простую структуру папок, чтобы не хранить все в одной папке и не наткнуться, опять же, на ограничение файловой системы. Что касается кеширования, то нет ничего более быстрого, чем ядреный файловый кеш ☝ общеизвестен факт, что он быстрее, чем даже хренение в memcached. Плюс устаревание записей кеша в случае с kernel file cache дается нахаляву, автоматически, а в случае с внешним кешем устареванием еще нужно отдельно управлять.

вот честно хотел бы на проект глянуть в итоге. что получится)))