..
Доброго здравия всем. Часто наверно мноие слышали, что после переиндексации базы данных она работает быстрее и т.п. А в некоторых случаях без переиндексации она неправильно работает или вообще не работает!
Как известно индексация используется для более быстрого доступа к данным, обычно к статическим, в справочниках или в уже накопленных данных. Предположим что в базе данных есть таблица с клиентами, в которой хранится такая информация как фамилия, имя, телефонный номер и прочее. Величина по которой выполняется индексация называется индексом. Например, телефонный номер может быть индексом, т.к. часто клиента привязывают по тел. номеру.
..
ТЕОРИЯ ИНДЕКСАЦИИ
..
Для простоты рассмотрим в качестве индекса просто ид. клинта, например. Пусть он представляет собой 32х битное беззнаковое целое число, это позволит присвоить ид. для чуть более чем 4 миллиарда клиентов. Этого для любой базы хватит, даже половина земного шара людей будут клиентами.
Идём далее. Для простоты рассмотрим модель индексации на примере индексации по первым 3м битам, ими будет адресовано не 4 миллиарда ид, а всего 8, см. изображение ниже.
В теории индексации используется дерево индексации из "объектов узлов" и "объектов доступа" к данным, которые ссылаются на данные, см. изображение выше. Если, например, нужно получить доступ к данным с ид. 101, то нужно перебрать только 3 объекта узла, а не все 8мь объектов доступа. Для 4х миллиардов записей чтобы получить доступ к произвольному объекту доступа нужно перебрать только 32 объекта узла, а не все 4 миллиарда объектов доступа. Вот в чём мошь индексации.
Как это работает. У каждого однотипного объекта узла есть два указателя, "p0" и "p1". Первый из них ("p0") указывает на ВСЕ объекты доступа по дереву, у которых самый младший нулевой бит ид. НУЛЕВОЙ. Второй "p1" указывает на все объекты доступа, у которых младший бит в ид. клиента равен единице. Получается что для адресации объектов доступа на первом шаге используется только один объект узла.
Для адресации к соотв. объекту доступа по 2му биту на втором шаге уже используется 2 объекта узла (см. шаг 2 на изображении). В зависимости от того чему он равен, 0 или 1, переход на следующий шаг идёт также через указатели "p0" или "p1", соответствующих структур.
Для адресации к соотв. объекту доступа по 3му биту всё тоже самое, только это ближе к цели и уже в другом соответствующем месте дерева.
Для адресации 32х битного ид. (клиента) используется 2 миллиона объектов доступа, но тут ничего страшного нет, для того чтобы это обойти есть разряжённые деревья, но это уже отдельная тема.
..
ИНДЕКСАЦИЯ В ТЕЛЕФОНИИ НА ЛЕТУ
..
С одной стороны это странно. Зачем нужен доступ к текущим вызовам по индессам, а не к какой-нибудь базе данных клиентов, по индексному тел. номеру клиента, например.
Для двух-трёх одновременных вызовов смысла в этом нет, а вот если их тысяча, и софтсвитчу (например, FreeSWITCH'у) прийдётся каждый раз перебирать всех их последовательно (перебирать соответствующие объекты) чтобы найти вызов с нужным ид. Тут уже метод последовательного перебора может затыкаться, а выход из данной ситуации является индексация по ид. вызовов на лету.
Как это работает. Рассмотрим изображение, см. выше. Напомню что для простоты на изображении есть только 8мь возможных ид. вызова из 3х бит, на практике это 4 миллиарда возможных ид. из 32х бит. На схеме выше для примера есть только 3 объекта доступа, с красными ненулевыми указателями на объекты вызовов, это ид. 000, ид. 101 и ид. 111, остальные отмечены серым, они нулевые, т.е. в реале вызовов с такими остальными ид. нет.
Если приходит сигнальное сообщения, с определнным ид. вызова, то сервер телефонии проходит по дереву и в 3 перебора (т.е. шага) находит соотв. "объект доступа". Если такой вызов есть, то сообщение прицепляется к соотв. объекту вызова по красному указателю и пусть соотвествующий поток дальше с ним разбирается. Если такого нет, то возвращается сообщение об ошибки или создаётся новый вызов, в зависимости от типа сообщения.
Таким образом, для 1000 одновременных вызовов, для распределения входящих сообщений между вызовами в частности, прийдётся перебрать не все 1000 объектов доступа, а только 10 объектов узлов. Это значительно ускорит работу, хотя реализация сложнее, но как есть.
Такая модель индексации в телефонии, постарался не писать ничего лишнего, чтобы не смешивать всё в кучу.