Pull to refresh

Древовидные СУБД

Reading time 7 min
Views 3.8K
Приглашаются к обсуждению все, имеющие опыт использования, в качестве хранилища данных, древовидных СУБД. Было бы полезно делится опытом разработки древовидных структур, описанием конкретики построения дерева индексов и алгоритмов полнотекстового поиска информации внутри хранилища данных.

Поскольку любая компьютерная система с целью оптимизации обмена производит обмен между памятью и диском в виде блоков, то атомарным элементом, хранящим данные на диске, является блок. Ни для кого не секрет, что многие СУБД (тот же ORACLE и MSSQL) фактически хранят данные в Б-деревьях. Б-дерево – это набор логически связанных блоков, выстроенных в иерархию, на каждом уровне которой определены блоки, у каждого из которых одинаковое количество уровней потомков. Описание алгоритма работы Б-дерева выходит за рамки данного блога.

Реляционный, объектный или прямой доступ обеспечивается логической моделью. Попробую предположить, что разумное использование логической модели данных, максимально приближенной к фактическому хранению – позволит более просто и быстро обрабатывать низкоуровневые данные, чем использование других логических моделей(SQL и пр.), хотя и существенно повышаются требования к уровню разработки механизмов доступа к данным. Возможно, что прямой доступ может быть представлен логическим деревом. Примером логического дерева данных – является глобал в СУБД Cache.

Приведу несколько примеров использования, из личного опыта, древовидных структур данных (глобалов).


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

Опишем структуру данных в виде глобала. В приведённом ниже описании не встречается никаких служебных слов и символов кроме:
  1. s — комманда set (установить)
  2. ^ — символ глобалла (логического дерева)
  3. [] — пространство имён (может быть определено на удалённом сервере)
  4. $$$ — пользовательская константа

описание структуры Транспортного Средства
//---------------------------UniVehicleModel---------------------------------------
//Идентификатор марки ТС
s ^[$$$MEDIA]$$$mBodyMediaGlobal($$$mType,"UniVehicleModel","@p","makeId")="id."

//Идентификатор модели ТС
s ^[$$$MEDIA]$$$mBodyMediaGlobal($$$mType,"UniVehicleModel","@p","modelId")="id."

//Год выпуска ТС
s ^[$$$MEDIA]$$$mBodyMediaGlobal($$$mType,"UniVehicleModel","@p","year")="ta."

//Тип кузова ТС
s ^[$$$MEDIA]$$$mBodyMediaGlobal($$$mType,"UniVehicleModel","@p","bodyTypeId")="id."


описание объявления (только автомобильная тематика)
//-----------------Вариации объявлений------------------------------------
//CarClassified
s ^[$$$MEDIA]$$$mBodyMediaGlobal($$$mType,"CarClassified")="variationType"
s ^[$$$MEDIA]$$$mBodyMediaGlobal($$$mType,"CarClassified","@t")="Classified"

//--------------------------------Classified---------------------------------------------
//Объявление содержит в себе цену
s ^[$$$MEDIA]$$$mBodyMediaGlobal($$$mType,"Classified","@p","Price")="enclosure"

//Список контактов
s ^[$$$MEDIA]$$$mBodyMediaGlobal($$$mType,"Classified","@p","contactList")="list"

//Список изображений
s ^[$$$MEDIA]$$$mBodyMediaGlobal($$$mType,"Classified","@p","imageList")="list"

//Дополнительный текст
s ^[$$$MEDIA]$$$mBodyMediaGlobal($$$mType,"Classified","@p","additionalText")="s."

//Идентефикатор рубрики
s ^[$$$MEDIA]$$$mBodyMediaGlobal($$$mType,"Classified","@p","rubricId")="id."

//Вариация легковое авто включает в себя ТС
s ^[$$$MEDIA]$$$mBodyMediaGlobal($$$mType,"Classified","@v","CarClassified","@p","UniVehicleModel")="enclosure"


Как видим из описания структуры объявления (Classified) в нём содержится список контактов. Но контакты могут иметь различные вариации:
  1. телефон
  2. e-mail
  3. адрес
  4. GPS
  5. другие контакты

Что не отображено в описании структуры объявления, но описано в структуре контакта:
//------------------------------------Contact-------------------------------------
//Имя контактной персоны
s ^[$$$MEDIA]$$$mBodyMediaGlobal($$$mType,"Contact","@p","contactPerson")="ta."

//Вариация GPS
s ^[$$$MEDIA]$$$mBodyMediaGlobal($$$mType,"Contact","@v","GPSContact","@p","GPS")="enclosure"

//Вариация телефонный контакт
s ^[$$$MEDIA]$$$mBodyMediaGlobal($$$mType,"Contact","@v","PhoneContact","@p","Phone")="enclosure"

//Вариация адресный контакт
s ^[$$$MEDIA]$$$mBodyMediaGlobal($$$mType,"Contact","@v","AddressContact","@p","UniRealEstateAddress")="enclosure"

//Вариация веб-контакт
s ^[$$$MEDIA]$$$mBodyMediaGlobal($$$mType,"Contact","@v","WebSiteContact","@p","WebSite")="enclosure"

//Вариация eMail-контакт
s ^[$$$MEDIA]$$$mBodyMediaGlobal($$$mType,"Contact","@v","eMailContact","@p","eMail")="enclosure"

//---------------------Вариации контактов-------------------------------
//AddressContact
s ^[$$$MEDIA]$$$mBodyMediaGlobal($$$mType,"AddressContact")="variationType"
s ^[$$$MEDIA]$$$mBodyMediaGlobal($$$mType,"AddressContact","@t")="Contact"

//PhoneContact
s ^[$$$MEDIA]$$$mBodyMediaGlobal($$$mType,"PhoneContact")="variationType"
s ^[$$$MEDIA]$$$mBodyMediaGlobal($$$mType,"PhoneContact","@t")="Contact"

//GPSContact
s ^[$$$MEDIA]$$$mBodyMediaGlobal($$$mType,"GPSContact")="variationType"
s ^[$$$MEDIA]$$$mBodyMediaGlobal($$$mType,"GPSContact","@t")="Contact"

//WebSiteContact
s ^[$$$MEDIA]$$$mBodyMediaGlobal($$$mType,"WebSiteContact")="variationType"
s ^[$$$MEDIA]$$$mBodyMediaGlobal($$$mType,"WebSiteContact","@t")="Contact"

//eMailContact
s ^[$$$MEDIA]$$$mBodyMediaGlobal($$$mType,"eMailContact")="variationType"
s ^[$$$MEDIA]$$$mBodyMediaGlobal($$$mType,"eMailContact","@t")="Contact"


Прошу прощения за обилие непонятного кода в этом блоге, но предположим что нам необходимо расширить систему (газету объявлений) и включить в неё предметную область недвижимость. Достаточно добавить описание новой вариации объявления:
//-----------------Вариации объявлений--------------------------------------------
//RealEstateClassified
s ^[$$$MEDIA]$$$mBodyMediaGlobal($$$mType,"RealEstateClassified")="variationType"
s ^[$$$MEDIA]$$$mBodyMediaGlobal($$$mType,"RealEstateClassified","@t")="Classified"

//Вариация недвижимость содержит в себе объект недвижимости
s ^[$$$MEDIA]$$$mBodyMediaGlobal($$$mType,"Classified","@v","RealEstateClassified","@p","UniRealEstate")="enclosure"


И добавить описание структуры объекта рынка недвижимости:
//---------------------------------------UniRealEstate------------------------------------------
//Этажность объекта недвижимости
s ^[$$$MEDIA]$$$mBodyMediaGlobal($$$mType,"UniRealEstate","@p","floorQuanity")="n."

//Этаж объекта недвижимости
s ^[$$$MEDIA]$$$mBodyMediaGlobal($$$mType,"UniRealEstate","@p","floorNumber")="n."

//Тип планировки
s ^[$$$MEDIA]$$$mBodyMediaGlobal($$$mType,"UniRealEstate","@p","housePlaningType")="ta."

//Общая площадь
s ^[$$$MEDIA]$$$mBodyMediaGlobal($$$mType,"UniRealEstate","@p","totalArea")="ta."

//Высота потолков
s ^[$$$MEDIA]$$$mBodyMediaGlobal($$$mType,"UniRealEstate","@p","cellingHight ")="ta."
//------------------------------------------------------------------------------------------------------------------


Структура описана.

Возможно я выбрал не самые удачные служебные флаги для описания:
  1. "@t" — типов
  2. "@p" — свойств
  3. "@v" — вариаций
  4. «list» — списков
В любом случае их легко заменить на более правильные.

В дальнейшем можно легко углубляться в описание требуемой предметной области: будь то контакты, автомобили, недвижимость и прочее. Разумеется, также необходим рекурсивный механизм обработки структуры, который на основании описанного выше дерева, выполняет запись чтение и обновление данных. То есть на вход приходит тело (например xml) механизм бежит по дереву тела на входе, сравнивает его с деревом хранения описания структуры — и выполняет обработку. Написание такого алгоритма не составит труда для программиста с некоторым опытом, и я не буду приводить свой код для этого механизма — так как уверен существуют более достойные примеры. Одно из преимуществ хранения описания структуры данных в виде логического дерева в том — что механизмы обработки данных ничего не знают о предметной области (о входных данных), которая может развиваться по мере накопления знаний. Конечно, знание о предметной области — в некотором виде должно находится на уровне интерфейса (возможно использовать подобные структуры) — однако все механизмы внутри системы(в том числе CRUD механизмы, механизмы индексации и поиска) не привязаны к предметной области (ничего не знают о структуре данных).

Разумеется описания структуры данных в дереве недостаточно, для данного блога. В ближайшее время планирую описать хранение данных и поисковых индексов в деревьях. Также в глобале описания структуры очень удобно хранить правила (имена функций), которые должны рекурсивно вызываться на этапе обработки данных — и могут влиять на путь обхода структуры.Буду признателен за справедливую критику. Готов ответить на уточняющие вопросы.

Методология описанная в данном блоге, в той или иной степени, используется в живом интернет проекте.
Tags:
Hubs:
+5
Comments 24
Comments Comments 24

Articles