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



В статье рассказано о моей попытке поиска универсального решения.

Пусть нам, например, необходимо отобразить некоторые данные из двух связанных таблиц:



Стандартный подход обычно состоит из следующих шагов:

1. На сервере написать SQL-запрос с JOIN-ом
2. На сервере добавить для него функцию, возвращающую массив объектов, и сделать ее доступной через routes
3. На клиенте добавить AJAX-вызов к серверу, и отрисовку полученного результата в таблицу

Недостатки стандартного подхода мне видятся в следующем:

1. SQL-запрос и функция-обертка должны учитывать возможные коллизии имён колонок, т. е. нельзя просто сделать "SELECT *".
2. Ответ сервера будет содержать большое количество дублирующихся записей из связанных таблиц. В нашем примере запись с ключем «sales» из таблицы departments будет передана два раза.
3. При связи большого количества таблиц мы или получим длинные ключи, что приведет к увеличению бесполезного расхода памяти и трафика по передаче этих ключей, или имена колонок в SQL-запросе необходимо перечислять вручную, что приведет к дополнительным издержкам при внесении изменений в структуру БД.
4. Количество функций API для получения данных из связанных таблиц может значительно превысить количество таблиц, что ведет к раздуванию кода, и, как следствие, издержкам.

Нестандартный подход — получить таблицы по отдельности и связать их на клиенте. Иногда это можно сделать легко. Например, в приведенной выше структуре можно загрузить таблицу «departments» в хеш, и осуществлять доступ по «id». Но чаще этого сделать нельзя, и приходится пользоваться различными функциями поиска типа Array.find или Array.indexOf.

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

Подход, при котором сервер выдает нам нормализованные таблицы, а мы потом их связываем в JavaScript-коде, показался мне более привлекательным. Не хватало только инструмента, чтобы их легко связывать. Я отложил все дела и сел его писать.

Требования получились следующие:

• Инструмент должен позволять мне создавать произвольные индексы на массив, и поддерживать их в актуальном состоянии.
• Инструмент должен уметь искать в массиве по индексам, по возможности без медленных операций перебора элементов.
• Интрумент должен уметь соединять массивы по индексированным полям в соответствии с неким объектом-декларацией, что-то типа оператора JOIN в SQL, но без парсинга запросов и всей мощи, предлагаемой SQL.

Так появились Strelki.js, и пока единственный в нем класс — IndexedArray.

Итак, создадим новый IndexedArray:

var emp = new StrelkiJS.IndexedArray();

Добавим в него данные:

    emp.put({
	    id: "001",   
	    first_name: "John",     
	    last_name: "Smith",   
	    dep_id: "sales", 
	    address_id: "200"
	});
	emp.put({
		id: "002",   
		first_name: "Ivan",    
		last_name: "Krasonov",   
		dep_id: "sales", 
		address_id: "300"
	});

Посмотрим, что внутри:



Под капотом IndexedArray представляет из себя хеш (this.data), куда сохраняются ссылки на объекты. В качестве ключа хеша используется поле «id» сохраняемого элемента, которое должно быть уникально. Так как многие современные серверные фреймворки также используют поле «id» подобным образом, то это ограничение не должно стать проблемой.

Кроме того, в IndexedArray имеется хеш this.indexData. Ключи этого хеша содержат название индексируемого поля, а значения — хеши с ids соответствующих элементов основного хеша. Пока индексов у нас нет, поэтому this.indexData пуст.

Добавим индекс:

emp.createIndex("dep_id");

Посмотрим this.indexData:



this.indexData теперь содержит ключ «dep_id», который содержит данные индекса в виде вложенных хешей.

Поищем что-нибудь по индексу:

> emp.findIdsByIndex("dep_id","sales")
< ["001", "002"]

В отличие от функций типа Array.find, индексный поиск не использует перебор данных, а только хеши, что позволяет добиться высокой скорости. Замеры, правда, я пока не делал, но должно работать быстро.

Добавим еще данных:

emp.put({
    id: "003",   
    first_name: "George",   
    last_name: "Clooney",    
    dep_id: "hr", 
    address_id: "400"
});
emp.put({
    id: "004",   
    first_name: "Dev",   
    last_name: "Patel",    
    dep_id: "board", 
    address_id: "500"
});

Найдем элементы по индексу, и сформируем из них новый IndexedArray:

var sales_emp = emp.where("dep_id","sales");

Создадим и заполним еще один IndexedArray:

var adr = new StrelkiJS.IndexedArray();
adr.put({  id: "200",  address: "New Orleans, Bourbon street, 100"});
adr.put({  id: "300",  address: "Moscow, Rojdestvensko-Krasnopresnenskaya Naberejnaya"});
adr.put({  id: "500",  address: "Bollywood, India"});

Связывание массивов

Для описания связи данного IndexedArray с любым другим служит объект следующего вида:

{
        from_col: "address_id", // поле в данном IndexedArray
        to_table: adr,          // ссылка на связываемую таблицу
        to_col: "id",           // "id", или другое индексированное поле в связываемой таблице
        type: "outer",          // "outer" для LEFT OUTER JOIN, или null для INNER JOIN
        join:                  // null или ссылка на массив точно таких же объектов описания связи, для построения вложенных JOIN-ов
}

Присоединим adr к emp JOIN-ом:

var res = emp.query([
    {
        from_col: "address_id", // name of the column in "emp" table
        to_table: adr,          // reference to another table
        to_col: "id",           // "id", or other indexed field in "adr" table
        type: "outer",          // "outer" for LEFT OUTER JOIN, or null for INNER JOIN
        //join: [               // optional recursive nested joins of the same structure
        //    {
        //        from_col: ...,
        //        to_table: ...,
        //        to_col: ...,
        //        ...
        //    },
        //    ...
        //],
    }
])

Аналогичный оператор на SQL выглядел бы так:

SELECT ...
FROM emp
LEFT OUTER JOIN adr ON emp.address_id = adr.id

Результат будет выглядеть так:

[
    [
        {"id":"001","first_name":"John","last_name":"Smith","dep_id":"sales","address_id":"200"},
        {"id":"200","address":"New Orleans, Bourbon street, 100"}
    ],
    [
        {"id":"002","first_name":"Ivan","last_name":"Krasonov","dep_id":"sales","address_id":"300"},
        {"id":"300","address":"Moscow, Rojdestvensko-Krasnopresnenskaya Naberejnaya"}
    ],
    [
        {"id":"003","first_name":"George","last_name":"Clooney","dep_id":"hr","address_id":"400"},
        null
    ],
    [
        {"id":"004","first_name":"Dev","last_name":"Patel","dep_id":"board","address_id":"500"},
        {"id":"500","address":"Bollywood, India"}
    ]
]

Как видим, связывание массивов превратилось из функций с циклами и переборами в простую декларацию связей.

Ограничения

IndexedArray не хранит копии объектов, а только лишь указатели на них (отсюда и название Strelki). Поэтому, если объект был помещен в IndexedArray методом put(), а затем изменен, информация в индексах может стать некорректной. Чтобы избежать этой ситуации необходимо удалить объект из IndexedArray методом del() перед изменением.

Связывание может осуществляться только по индексированному полю, либо по полю «id».

Некоторые методы объекта IndexedArray (например length()) требуют построения массива ключей «id». При этом массив ключей сохраняется в объекте для возможного повторного использования. При каждом изменении массива (методы put(), del(), и т.п.) массив ключей обнуляется. Поэтому чередование методов, которые создают и затем обнуляют массив ключей, может привести проблемам производительности на больших наборах данных.

Планы

StrelkiJS создан для облегчения написания основного проекта KidsTrack, о котором я писал на хабре ранее. Поэтому все решения о новом функционале пока диктуются потребностями родительского проекта. В ближайших планах — сделать более удобный доступ к колонкам в результатах JOIN-а,

Где скачать

Github: github.com/amaksr/Strelki.js
Песочница: www.izhforum.info/strelkijs