Каков наиболее эффективный способ хранения и запроса деревьев?

Question

Мне нужно проанализировать 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)

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

Answer 1

Прежде чем инвестировать слишком много времени в разработке иерархической структуры данных поверх реляционной базы данных, рассмотрит чтение "Naive Trees" section (starting at slide 48) в отличной презентации SQL антишаблонов Strike Back Билл Karwin. Билл описывает следующие методы для разработки иерархии:

1. Path перечисления (слайд 55)
2. вложенных наборов (слайд 58)
3. Закрытия таблицы (слайд 68)

Answer 2

Возможно, вы захотите проверить тип данных HIERARCHYID в SQL Server 2008 или его эквивалент в Oracle.

Answer 3

Дерев, как правило, не очень эффективен в базах данных. Я имею в виду: если вы создадите дерево, чтобы быть действительно рекурсивным, с элементами, указывающими на их родителей, вы получите много запросов, чтобы найти все под-узлы.

Но вы можете оптимизировать дерево, в соответствии с вашими потребностями.

Поместите любую часть 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.

Answer 4

В книге The Art of Sql от Stephane Faroult есть замечательная глава (7 - Работа с иерархическими данными), которая объясняет и сравнивает 3 метода хранения и запросов деревьев с использованием реляционных баз данных.

Если вы занимаетесь серьезной промышленной индустрией, изучение этой главы будет потрачено достаточно долго.

Answer 5

Я думаю, что наиболее эффективным способом хранения данных этого типа является таблица с разбивкой деталей (или иерархией).

Таблица взрывов деталей состоит из трех столбцов: идентификатор, родительский элемент и описание. Для примера данных, таблица будет выглядеть примерно так:

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 

Я считаю, что вы можете ответить на все ваши вопросы, начиная с этих двух таблиц.