примерный конспект того что я читал про специальные структуры в СУБД
-----------
11. Работа со специальными структурами в СУБД
********************************************************************
1. работа с деревьями
работа с древовидными структурами - канонический пример
задачи которая плохо решается средствами обычного SQL.
Обычная реализация - таблица имеет ссылку на папу (возможно на саму себя)
(примеры: дерево разделов магазина, дерево постов в обсуждении и т.п.).
конкретная проблема - невозможность одним запросом найти все листья
данного узла дерева.
дополнительные проблемы:
последовательность insert, delete, update
вариант организации для фиксированного количества уровней
вариант с рекурсивныйм представлением при помощи "виртуального View"
вараинты использования BTree для работы с деревьями
индекс - строка
индекс - правое и левое число для поддерева (вложенные множества - nested sets)
специальный синтаксис для работы с деревьями
------------------
В Oracle также реализованы так называемые древовидные запросы, предназначенные для работы с данными, организованными в виде дерева. Для реализации дерева в виде таблицы в ней должно быть дополнительных два поля: id узла и id родительского узла. Также должен быть корень (корни). Для реализации древовидных запросов имеются два дополнительных предложения:
START WITH - для идентификации коренных строк
CONNECT BY - для связи строк-потомков и строк-предков
В предложении CONNECT BY реализован также оператор PRIOR который используется для обозначения выражения-родителя.
Оператор SELECT, осуществляющий древовидный запрос, может использовать псевдостолбец LEVEL, содержащий уровень вложенности для каждой строки. Для коренных записей LEVEL=1, для потомков коренных записей LEVEL=2 и и.д.
SELECT LPAD(' ',2*(LEVEL-1)) || ename org_chart, empno, mgr, job
FROM emp
START WITH job = 'PRESIDENT'
CONNECT BY PRIOR empno = mgr;
ORG_CHART EMPNO MGR JOB
------------ ---------- ---------- ---------
KING 7839 PRESIDENT
JONES 7566 7839 MANAGER
SCOTT 7788 7566 ANALYST
ADAMS 7876 7788 CLERK
FORD 7902 7566 ANALYST
SMITH 7369 7902 CLERK
BLAKE 7698 7839 MANAGER
ALLEN 7499 7698 SALESMAN
WARD 7521 7698 SALESMAN
MARTIN 7654 7698 SALESMAN
TURNER 7844 7698 SALESMAN
JAMES 7900 7698 CLERK
CLARK 7782 7839 MANAGER
MILLER 7934 7782 CLERK
------------------
ссылки:
http://sdm.viptop.ru/articles/sqltrees.html
http://gzip.rsdn.ru/article/db/Hierarchy.xml
http://www.webscript.ru/stories/04/09/01/8197045
http://www.infocity.kiev.ua/db/content/ ... ml?id=2330
********************************************************************
2. работа с геометрической информацией (средствами обычных индексов, средствами специальных структур)
постановка проблемы (стандартные функции поиска фигуры в данном объёме пространства)
варианты организации специального индекса (равные кластеры, тернарные деревья и т.п.)
вариант использования обычного BTree для индексирования пространственной информации
Spatial data в MySQL, PostreesSQL, Oracle
http://dev.mysql.com/doc/refman/6.0/en/index.html
********************************************************************
3. работа с астрономической информацией (PostgresSQL)
расширение Spatial Data для радиальной системы координат (углы, расстояние)
********************************************************************
4. работа с полнотекстовым поиском
http://dev.mysql.com/doc/refman/6.0/en/ ... earch.html
-----------
mysql> CREATE TABLE articles (
-> id INT UNSIGNED AUTO_INCREMENT NOT NULL PRIMARY KEY,
-> title VARCHAR(200),
-> body TEXT,
-> FULLTEXT (title,body)
-> );
Query OK, 0 rows affected (0.00 sec)
mysql> INSERT INTO articles (title,body) VALUES
-> ('MySQL Tutorial','DBMS stands for DataBase ...'),
-> ('How To Use MySQL Well','After you went through a ...'),
-> ('Optimizing MySQL','In this tutorial we will show ...'),
-> ('1001 MySQL Tricks','1. Never run mysqld as root. 2. ...'),
-> ('MySQL vs. YourSQL','In the following database comparison ...'),
-> ('MySQL Security','When configured properly, MySQL ...');
Query OK, 6 rows affected (0.00 sec)
Records: 6 Duplicates: 0 Warnings: 0
mysql> SELECT * FROM articles
-> WHERE MATCH (title,body)
-> AGAINST ('database' IN NATURAL LANGUAGE MODE);
-----------
********************************************************************
5. нечёткий текстовый поиск, синонимы, алгоритм Левенштэйна, soundex и т.п.
обратный индекс словоформ, примерное устройство индекса
учёт окончаний, учёт орфограйии
********************************************************************
6. работа с базами документов и файлов произвольного вида (картинками, офисными форматами)
вариант - хранение на диске
преимущество: распределённость, много места, легко добавлять ещё места
недостатки: нужно специально учитывать при backup ах и репликации
вариант - хранение в базе
преимущества: обычный бэкап, обычная репликация, простая работа
недостатки: сложность с переполнением базы, проблемы при передаче по сети
больших объёмов данных
********************************************************************
7. работа с файловой системой и обеспечение целостности данных при работе с ней
учёт сетевых имён
учёт при бэкапе и репликации
********************************************************************
8. работа с очень большими блоками данных в разных СУБД и проблемы при закачивании
их одним запросом
опции СУБД "максимальный пакет"
варианты решения
закачивание текстовых файлов порциями
********************************************************************
9. T-деревья
сбалансированные деревья "полностью в памяти"
MSSQL, Oracle
********************************************************************
10. шифрование и обеспечение секретности
шифрование трафика
шифрование самой базы данных
шифрование всего диска