осторожно βeta версия!

ТИЦ, байт и 12 лет истории. Казалось бы что общего?

Во время проектирования базы данных для большого эксперимента с ТИЦ, была замечена интересная особенность, позволяющая сэкономить несколько байт при хранении значений индекса цитирования. На момент создания базы я не придал этому особого значения, был увлечен разработкой, сейчас, в ожидании следующего апдейта, хотелось бы подробнее рассмотреть способ хранения.

Общеизвестно, что кратность значений ТИЦ не равномерно и увеличивается вмести с самим индексом цитирования. Ступени я собрал в табличку для наглядности и тех кто не знает.

группа от до шаг
1 0 250 10
2 275 500 25
3 550 1000 50
4 1100 10000 100
5 11000 100000 1000
6 110000 10000

Никогда не задумывался зачем такая система нужна, принимал её как что-то естественное, до того момента пока не возникла необходимость хранить большой объем данных с весьма не равномерным распределением. Всего лишь шесть тысяч сайтов имеет группы больше 4. 253 из них входят в 5 группу и всего лишь 7 в 6. Два байта могут хранить максимально значение 65 535 в десятичной системе. Отсюда следует, что для незначительного количества сайтов потребуется еще один байт, его добавление сдвигает максимальное значение до ~16,8 миллионов. Но нам столько не нужно! Максимальный ТИЦ на данный момент у самого Яндекса и составляет 220 000 единиц.

Какая разница сколько байт?

Значения ТИЦ для всех 120 миллионов доменов займут в базе данных для трех байт ~350Мб для одного 125Мб соответственно. Экономия весьма существенна с учетом того, что данные будут храниться для всех апдейтов и количество доменов постоянно растет.

Все уже придумано за нас.

Самый очевидный вариант: убрать последний ноль не подходил из-за второй группы с кратностью 25. Несколько часов размышлял как сократить занимаемый объем. В итоге выяснилось что зря, все уже придумано за нас. Понятно что я не первый кто столкнулся с этой проблемой, нужно всего лишь быть чуть внимательнее. Все помещается в один байт!

группа от до шаг в 1 байт
от
в 1 байт
до
1 0 250 10 0 25
2 275 500 25 26 35
3 550 1000 50 36 45
4 1100 10000 100 46 135
5 11000 100000 1000 136 225
6 110000 400000 10000 226 255

Вот так все просто. Байтовый ТИЦ укладывается в простую формулу для значений меньше 250:

байтовый тиц = истинный тиц/10

И чуть сложнее для остальных значений:

байтовый тиц = P-10 + истинный тиц/S
где
  • P - максимальное значение предыдущей группы
  • S - байтовый шаг текущей группы

Функция на php для кодирования выглядит следующим образом:

function ticEnc($tic) {
	switch ($tic) {
		case 0:	break;
		case ($tic <    250): $tic = $tic/10; break;
		case ($tic <    500): $tic = 15 + $tic/25; break;
		case ($tic <   1000): $tic = 25 + $tic/50; break;
		case ($tic <  10000): $tic = 35 + $tic/100; break;
		case ($tic < 100000): $tic = 125 + $tic/1000; break;
		case ($tic < 400000): $tic = 215 + $tic/10000; break;
		default : $tic = "ERROR";
	}
	return (int) $tic;
}

Скорость её работы вполне приемлема для небольших объемов. Чуть позже было найдено более элегантное и почти в 20 раз более быстрое решение, большей части читателей оно ни к чему, а кому очень надо сам догадается.

Размышления

Зачем была разработана подобная система хранения и когда?

Индекс цитирования появился в 1999 году. Скорее всего именно тогда и был придуман алгоритм его хранения. Причины внедрения тоже понятны - банальная экономия ресурсов. Средней домашней железкой тех времен был Celeron-300МГц с 64Мб оперативной памяти и жестким диском на 4 Гб. На серверах стояли 2xPentium II Xeon 400 МГц до 2Гб ОЗУ и SCSI RAID на пару десятков гигабайт.

Актуально спустя 12 лет?

Сложно сказать наверняка. Рунет за это время вырос на несколько порядков и расценивать все 225 тысяч сайтов с ТИЦ 10 как одинаковые было бы глупо. Возможно сейчас ТИЦ считается с точностью в 4 байта и может иметь отрицательное значение, но все равно округляется до шкалы 12 летней давности.

Комментарии (24)

Ваша оценка: Нет Средняя: 5 (4 голоса)
Аватар пользователя Гость

С чего это вдруг тиц может быть отрицательным? Меньше нуля не видел не разу. Статья чушь как и все остальные.

Аватар пользователя webpavilion

Статья как бы не о том совсем. Если вы что-то не видели, или не знаете о том, что это что-то существует это вовсе не значит что его нет. Не нравиться не читай те, я не заставляю.

Аватар пользователя Гость

Интересно было почитать, хотя практическое применение данной инфе все ж трудно найти. Так, для общего развития в плане применения к другим задачам прогграммирования...
ps C ошибками в тексте что-то надо делать, хотя бы в Ворде проверяйте.
pps Дизайн сайта очень хорош, черт возьми. Дайте побольше денег вашему дизайнеру.
ppps Я не дизайнер этого сайта.

Аватар пользователя Гость

Много буквов а толку... даешь практику! Из полезного только максимально значение тица в 400К

Аватар пользователя Гость

Уважаемые! если вы ни хрена не понимаете, то лучше не заходите на этот блог, тут каждая статья интереснее другой, я редко обращают на дизайн сайта, ну это совсем гумно, поменяйте пожалуста дизайн и поставьте счётчик!

Аватар пользователя webpavilion

Счетчики ставить не буду, блог некоммерческий, они тут не к чему. По поводу дизайна: примерно половине посетителей он нравится и самое главное, он нравится и мне тоже - менять кардинально нечего не буду.

p.s. Спасибо за положительный отзыв о качестве статей.

Аватар пользователя Гость

У всех блог сначала "некоммерческий", одна радость через полгодика не будет видно глупых статей за баннерами.

Аватар пользователя webpavilion

Кто то заставляет вас смотреть на статьи сейчас? Зачем ждать полгода? Не заходите на мой блог если он вам так не нравится.

Аватар пользователя Гость

как ИЦ может быть меньше нуля?) смысл харнить такое значение?

Аватар пользователя webpavilion

Вроде простые вопросы вы задаете но к сожалению не могу на них ответить кратко, объяснений на целую статью, а то и две.

Аватар пользователя Гость

на самом деле все логично. Тиц сайта - параметр, который есть у всех сайтов и в случае с отпицательным значением, сайту придется набрать больше ссылок/веса/траста (или того, что влияет на рост ТИЦ).

Аватар пользователя Гость

Поддерживаю-что ни статья-зачитаешься! А дизайн, прост и талантлив.

Аватар пользователя Гость

Привет с серча, товарищи!!!

Аватар пользователя Гость

Очень интересная статья. Я даже и не знал половины всего этого. До таких значений тиЦ мне далеко, так что мне по 10 долго изменение наблюдать

Аватар пользователя Гость

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

Аватар пользователя webpavilion

Мне кажется вы просто его плохо знаете.

Аватар пользователя Гость
Хорошие статьи. Автор спасибо тебе. Это его мнение и он его никому не навязывает и не утверждает в 100% их верности. Каждый делает выводы для себя сам где он прав, а где нет... Сам факт того, что подобный анализ никто не взялся проводить.... А эти данные могут пригодиться...... не фак что сегодня, может завтра.... Спасибо автору за статьи!!!!
Аватар пользователя Гость
Не статья а бред! 120 или 360 мегабайт на значение тица -- какая разница. Когда имена доменов гораздо большое занимают: Допустим средняя длина домена 20 букв, тогда 120 * 10^6 на на 21 байт получаем 2.5 Гбайт. так что экономия 240 мбайт это 8% не так много...
Аватар пользователя webpavilion
Открою вам страшную тайну в реляционных БД есть волшебное понятие нормализации данных. Я бы на вашем месте не выносил, так открыто, свое невежество на показ. Таблица с историей одного апдейта (вместе с индексами) весит ~220Мб и экономия в 240Мб составляет более 100%, будете спорить, что это много?
Аватар пользователя Гость
открою вам страшную тайну, в поиске не используются реляционные БД.
Аватар пользователя webpavilion
а какие используются?
Аватар пользователя Гость
В поиске используется инвертированный индекс. Для хранения тица я думаю что хеш. В вашем случае, если не нужен доступ по ключу, лучше хранить в текстовом виде. если нужно хранить историю то можно join ом склеить несколько дат. Краткое описания основных структур данных: http://guap.ru/dept04/caf46/textbooks/str_alg/index3.htm Очень хорошая книга, если хотите узнать как устроены поисковые машины: http://www.ozon.ru/context/detail/id/5497130/
Аватар пользователя webpavilion
Инвертированный индекс это тип хранимых данных а вот храниться он как раз в БД, вы видимо книжку не дочитали ещё. Какое отношение ваши предположения о работе ПС имеют к моей реализации, спроектированной именно для удобных выборок по интервальным значениям? В чем вы видите противоречия использования "байтового ТИЦ" для хранения и хеша для его выборки?
Аватар пользователя Гость
nugops, не стоит показывать свои незнания там, где не сильны. глупо выглядит. > 120 или 360 мегабайт на значение тица -- какая разница купить хлеб за 100 или 33 рубля, пройдя одно и то же расстояние?

Отправить комментарий