Яваскриптовое DAO

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

Зачем?

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

var objects= {
	'1': { a: 1, b: 2 },
	'2': { a: 2, b: 4 },
	'4': { a: 4, b: 8 }
}

Но что, если нам нужно из одного и того же множества объектов выбирать по разным полям в зависимости от ситуации? Тогда естественное решение - выделить один основной массив и к нему нужное количество хэш таблиц, выполняющих функции индексов. Естественно, изменения в них должны быть синхронизированными, а потому требуется единая точка входа для изменения объектов (как самого списка, так и значения полей). К этой же точке неплохо было бы подцепить и некоторые контроллеры, например: "не допускать дубликатов ключей" или "автоматически увеличивать значение определённого поля", - знакомые нам из реляционных баз данных. Кроме того, родные яваскриптовые хэши обладают одним существенным недостатком - в качестве ключей могут выступать только строки, а иногда очень хочется видеть в качестве ключей объекты. Ну а уж возможность искать объекты (с преемлемой скоростью) по запросам вида "значение должно быть больше такого-то" на хэшах вообще не реализовать.

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

Остановимся на трёх основных индексах поподробнее...

Каждый из них имеет методы insert и drop, принимащие на вход список объектов. Первый - добавляет указанные убъекты, второй - удаляет их из индекса. Метод select используется для выборки объектов по параметрам; у каждого индекса - свой набор параметров для селекта. Говорящие методы selectAll и dropAll быстро выбирают и удаляют все объекты, соответственно. Ещё один специфический метод - selectNdrop - делает выборку, удаляя выбранные объекты из индекса.

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

StringHash

В его основе лежат упомянутые в начале родные яваскриптовые хэш-таблицы, позволяющие задавать соответствие [текстовый ключ]->[массив значений].
Он подходит, когда нужно выбирать множество объектов, сформированные ключи которых равны, переданному в качестве параметра, значению.

ObjectHash

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

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

OrderedList

Архитектура упорядоченного списка схожа с объектным хэшем - тут также используется два массива: для ключей и для значений. Значения хранятся без группировки по ключу, как в ObjectHash, поэтому ключи могут повторяться, но, благодаря автоматической сортировке при добавлении, одинаковые ключи всегда идут подряд.

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

Ограничения

Куда ж без них?

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

Пишем своий индекс

Пусть у нас стоит такая задача: есть набор объектов (пользователей) с целочисленным полем ballance; и нужно периодически получать список пользователей с положительным баллансом.

Для этого можно было бы воспользоваться индексом OrderedList:

var ballancedUsers= new DAO.Index.OrderedList( 'ballance' );
// заполнение индекса
alert( ballancedUsers.select( 0 ) );

Однако, при этом каждый раз будет происходить бинарный поиск. Гораздо эффективнее было бы для этой задачи создать отдельный индекс:

var rightUsers= new function( ){
	this.dropAll();
}.hardExtend({
	insert: function( objects ){
		var index= this.index,
			length= objects.length;
		for( var i= 0; i < length; ++i ){
			var obj= objects[ i ];
			if( obj.ballance > 0 ) index.push( obj );
		}
	}
,
	selectAll: function( ){
		return this.index.slice( 0 );
	}
,
	dropAll: function( ){
		this.index= [];
	}
})
// заполнение индекса
alert( rightUsers.selectAll( ) );

Это неполная реализация описанного ранее интерфейса индексов, но её, однако, вполне может хватить в практических целях.
Тут стоит отметить, что проще и универсальнее было бы воспользоваться универсальным индексом StringHash, который был бы не многим более ресурсоёмок - в дополнение к массиву юзеров с положительным баллансом, он бы хранил и массив пользователей с нулевым или отрицательным балансом:

var rightUsers= new DAO.Index.StringHash( function( obj ){ return obj.ballance > 0 } );
// заполнение индекса
alert( rightUsers.select( true ) );

Вывод из этого можно сделать простой - не стоит изобретать велосипед, без крайней на то необходимости.

DAO

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

База данных поддерживает следующие методы:
insert - добавляет список объектов в базу. каждый объект, при этом, должен пройти через все контроллеры, после чего он добавляется в основной реестр объектов и в каждый зарегистрированный индекс.
selectAll - быстро достаёт все внесённые в базу данных объекты.
drop - удаляет переданные объекты из базы данных и всех индексов
dropAll - очищает базу данных.

Конструктор базы данных принимает на вход два параметра: хэш индексов и массив контроллеров. Любой из них можно смело опускать.

Использование индексов

Пусть мы определили базу данных следующим образом:

var users= new DAO({
	name: new DAO.Index.StringHash( 'name' ),
	age: new DAO.Index.OrderedList( 'age' ),
	role: new DAO.Index.StringHash( 'role' )
});

Теперь, используя метод insert базы данных, мы можем наполнить базу любыми объектами:

users.insert([{ name: 'кукарача', age: 1, role: 'таракан' }]);

А вот селекты делаются через индексы:

users.index.name.select( 'кукарача' );

Использование контроллеров

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

var nameIndex= new DAO.Index.StringHash( 'name' );
var users= new DAO({
	name: nameIndex,
	age: new DAO.Index.OrderedList( 'age' ),
	role: new DAO.Index.StringHash( 'role' )
},[
	new DAO.Controller.Unique( nameIndex );
]);

Теперь, при попытке вставить объект с ключём name, для которого уже есть объект в базе - вставка произведена не будет. Если мы хотим, как-то реагировать на такие ситуации, то можно добавить колбэк-функцию:

new DAO.Controller.Unique( nameIndex, function( obj ){
	throw 'Ахтунг!';
});

Естественно, ничто не мешает создать на базе существующего свой контроллер:

DAO.Controller.AutoInc= function( index ){
	this.basis= DAO.Controller.Unique( index, function( obj ){
		var objects= index.selectAll();
		obj.id= objects[ objects.length - 1 ].id + 1;
		return true;
	});
}.hardExtend({
	insert: function( obj ){
		return this.basis.insert( obj );
	}
});

И что это получилось?

А получилась та ещё хрень ^_^ Над интерфейсом взаимодействия между бд, индексами и контроллерами нужно ещё как следует подумать...

скачать эту либу ~10kB