Каков наиболее эффективный способ хранения и запроса деревьев?
Мне нужно проанализировать 1 ТБ + журналов веб-доступа и, в частности, мне нужно проанализировать статистику, относящуюся к запрошенным URL-адресам и подмножествам URL-адресов (дочерние ветки). Если возможно, я хочу, чтобы запросы были быстрыми по малым подмножествам данных (например, 10 миллионов запросов).
Например, если задан журнал доступа со следующими запрошенными URL-адресами:
/ocp/about_us.html
/ocp/security/ed-209/patches/urgent.html
/ocp/security/rc/
/ocp/food/
/weyland-yutani/products/
Я хочу делать запросы, такие как:
- Подсчитайте количество запросов на все "ниже" /ocp.
- То же, что и выше, но только запросы подсчета для дочерних узлов в /ocp/security
- Верните 5 наиболее часто запрашиваемых URL-адресов.
- То же, что и выше, кроме группы на произвольной глубине,
например. Для последнего запроса выше будет возвращена глубина 2 для данных:
2: /ocp/security/
1: /ocp/
1: /ocp/food/
1: /weyland-yutani/products/
Я думаю, что идеальным подходом, вероятно, было бы использование столбца DB и токенизация URL-адресов, чтобы для каждого элемента URL был столбец. Тем не менее, мне бы очень хотелось найти способ сделать это с помощью приложений с открытым исходным кодом, если это возможно. HBase - это возможность, но производительность запросов кажется слишком медленной, чтобы быть полезной для запросов в реальном времени (также, я действительно не хочу заниматься реинтеграцией SQL)
Я знаю, что есть коммерческие приложения для этого типа аналитики, но по разным причинам я хочу реализовать это самостоятельно.
Ответы
Ответ 1
Прежде чем вкладывать слишком много времени в разработку иерархической структуры данных поверх реляционной базы данных, рассмотрите раздел "Наивные деревья" (начиная со слайда 48) в отличной презентации SQL Anti-Patterns Strike Back by Bill Karwin. Билл описывает следующие методы для разработки иерархии:
- Перечисление пути (слайд 55)
- Вложенные наборы (слайд 58)
- Таблица закрытия (слайд 68)
Ответ 2
В базах данных деревья, как правило, не очень эффективны. Я имею в виду: если вы создадите дерево, чтобы быть действительно рекурсивным, с элементами, указывающими на их родителей, вы получите много запросов, чтобы найти все под-узлы.
Но вы можете оптимизировать дерево в соответствии с вашими потребностями.
Поместите любую часть URL-адреса в столбец, это неплохая идея. Вам необходимо ограничить глубину определенным количеством узлов. У вас могут быть индексы по любому столбцу, что делает его очень быстрым.
Запросы по такой структуре очень просты:
Select count(*) From Hits where node1 = 'ocp' AND node2 = 'security';
Введите статистику доступа:
SELECT node1, node2, count(*) as "number of hits"
FROM hits
GROUP BY node1, node2
ORDER BY count(*) DESC
вы получите
node1 node2 number of hits
'ocp' 23345
'ocp' 'security' 1020
'ocp' 'food' 234
'weyland-yutani' 'products' 22
Вы также можете сохранить URL-адрес, как он есть, и фильтровать с помощью регулярного выражения. Это более гибко, но медленнее, потому что у вас нет индексов. Вам нужно только ограничить всю длину URL-адреса, а не количество под-узлов.
Я думаю, вы могли бы сделать это с любой базой данных, достаточной для хранения большого количества данных. Например, MySql.
Ответ 3
Книга Искусство Sql от Stephane Faroult имеет очень отличную главу (7 - Работа с иерархическими данными), которая объясняет и сравнивает 3 метода хранения и запросов деревьев с использованием реляционных баз данных.
Если вы делаете серьезную, индустриальную реализацию, изучение этой главы будет потрачено хорошо.
Ответ 4
Я думаю, что самый эффективный способ хранения данных этого типа - в таблице взрыва (или иерархии) частей.
Таблица взрывов деталей состоит из трех столбцов: идентификатор, родительский элемент и описание. Для данных примера таблица будет выглядеть примерно так:
Identity Parent Description
0 Null ocp
1 0 about_us.html
2 0 security
3 2 ed-209
4 3 patches
5 4 urgent.html
6 2 rc
7 0 food
8 Null weyland-yutani
9 8 products
По мере заполнения таблицы URL (взрыва) запишите таблицу, в которой записывается лист каждого URL-адреса. Из данных примера:
Leaf ID
-------
1
5
6
7
9
Я считаю, что вы можете ответить на все ваши вопросы, начиная с этих двух таблиц.
Ответ 5
Возможно, вы захотите проверить тип данных HIERARCHYID в SQL Server 2008 или его эквивалент в Oracle.