Раньше я был разработчиком, защищающим замечательный продукт базы данных под названием MarkLogic , базу данных документов NoSQL для предприятия. Сейчас довольно часто люди спрашивают меня о базах данных.
Здесь я попытаюсь объяснить некоторые забавные вещи, которые вы можете сделать с индексами. Не собираюсь говорить о их реализации, а просто о том, что они решают.
Суть в том, чтобы помочь вам обдумать выбор, который вы делаете, когда внедряете что-то для ускорения ваших приложений. Я уверен, что если вы думаете, что идея умная и забавная, вы исследуете, каков наилучший алгоритм для ее реализации.
Если вам интересно узнать о MarkLogic, вы всегда можете проверить документ Inside MarkLogic .
Индексы диапазона
Наиболее частым типом индексов в базе данных являются индексы диапазона. Они позволяют вам делать очень быстрые заказы, подсчет, агрегирование и т. Д. Давайте подумаем об индексе местоположения. Я могу определить индекс, который говорит, что если документ содержит свойство json, называемое local, то добавьте это свойство в индекс диапазона, называемый location, рассматривая это значение как строку.
| Показатель | подсчитывать | документы |
| Алжир | 2 | КОМПАКТ ДИСК |
| Австралия | 1 | |
| Канада | 5 | А, В, С, D, Е |
| Португалия | 3 | А, В, С |
| Идти | 5 | В, С, D, Е, F |
Это означает, что документы C и D имеют местный Алжир и так далее. Так что теперь я могу попросить базу данных дать мне список стран по первой букве (включая частоты):
A (3) C (5) P (3) T (5)
Теперь вы можете отобразить это для пользователей, и они могут использовать его для детализации содержимого, даже если визуально невозможно отобразить все существующие опции. Вы также можете комбинировать это с другими визуализациями, которые, например, могут, например, выбирать местоположения в странах, начинающихся с буквы А и которыми управляют злые диктаторы. Вам просто нужно добавить еще один индекс в свойство json злых диктаторов.
Теперь, учитывая это, пользователь может нажать вкладку A (3). В индексе вы можете разрезать его и получить эти две строки документов. Теперь сделайте сортировку слиянием, и вы получите:
А, С, D
Значение документа A, C и D находится в странах, которые начинаются с буквы A.
Та же методика может использоваться для сортировки документов, выполнения быстрых агрегатов и т. Д. Обычно вы можете хранить кучу таких в памяти, поскольку они являются довольно скудными индексами, и если вы их создали, они, вероятно, понадобятся! Это техника, которая также позволяет вам делать диапазоны дат и выражать вещи, как в последние 3 дня, или в восьмидесятые годы (десятилетие) и т. Д. Очень круто и супер полезно.
Одна вещь, которую этот индекс не дает вам, это то, какие местоположения принадлежат документу A. Это было бы эквивалентно полному сканированию таблицы. Таким образом, вы можете создать другой способ, то есть связать документы с расположениями, которые у них есть. Для этого примера это будет:
| Документ | подсчитывать | Места |
| 3 | Австралия, Канада, Португалия | |
| В | 3 | Канада, Португалия, Того |
| С | 4 | Алжир, Канада, Португалия, Того |
| D | 3 | Алжир, Канада, Того |
Теперь довольно просто сказать, где находится документ А, не так ли? ? Так что просто создайте это бездействием, когда ваше использование запрашивает указатель диапазона на местоположение, и он может иметь оба. ?
Недостаток индексов диапазона заключается в том, что вы должны определить их, чтобы использовать их. Это означает, что если вы забудете создать индекс, а затем выполнить специальный запрос, производительность будет плохой. Или это будет тайм-аут. Вероятно, истечет время ожидания, если вы делаете что-либо серьезное с данными. Полное сканирование таблицы занимает много времени.
Перевернутый индекс
Инвертированные индексы — это то, что движет поисковыми системами сегодня, и для меня одна из самых революционных вещей, которые случались с базами данных до сих пор. Мы все согласны с тем, что полнотекстовый поиск — отстой в базах данных, верно?
Однако поисковые системы показали нам ценность этой структуры: дает мне любой текст в любой форме и задает любой вопрос и против слов, я могу ответить быстро. ВСЕ офигенный полный интернет. Да уж!
Перевернутый индекс отвечает на вопросы типа «найди меня», которые содержат слово «синий», но не «черный». Они вроде как указатель в конце книги. Вы можете просто увидеть, на каких страницах появляется слово «синий» (назовем его набором А), а затем на каких страницах появляется слово «черный» (набор В). Что мы ищем это:
А ИСКЛЮЧЕНИЕ B
И мы можем просто продолжать добавлять ограничения. Круто то, что с инвертированным индексом, чем больше условий вы добавляете, тем меньше детализация запросов, что обычно приводит к меньшему количеству операций ввода-вывода и загрузки процессора, что означает более быстрые запросы.
Инвертированный индекс очень похож на хеш-таблицу. Вы хешируете слово и помещаете его в хеш-таблицу. Затем, как и в индексе диапазона, вы сохраняете массив документа, который соответствует этому термину. В отличие от индекса диапазона инвертированный индекс хешируется, поэтому не упорядочен. В отличие от индекса диапазона, инвертированный индекс не является скудным и индексирует каждое слово, найденное в документе.
| Срок | Список терминов |
| красный | С |
| синий | А, В |
| черный | |
| бег | |
| Бег | ДО Н.Э |
Это хеш-таблица, неупорядоченная, и у вас нет доступа к ключам. Если вы запрашиваете слова, начинающиеся с буквы B, этот индекс бесполезен, вы можете найти вещи только после запуска их через хеш-функцию. Однако это делает такие вещи очень простыми. При хешировании вы можете объединить такие слова, как run, run, run к одному и тому же хешу. Это означает, что вы можете понять, что эти слова одинаковы для целей поиска непосредственно из индекса. На самом деле, если вы ставите термины перед хэшированием, вы теряете способность различать, было ли слово запущено или работает.
Каждый раз, когда вы вставляете документ, вам нужно пройти через каждое слово и добавить его в этот индекс. Таким образом, если у вас есть документ с 80 тысячами слов, этот документ вызывает 80 тысяч обновлений индекса. Это требует времени.
Поскольку вы не можете реально контролировать сложность алгоритма индексации (учитывая, что вы умный парень и реализовали наиболее эффективный алгоритм для своей задачи), все, что вы можете сделать, это контролировать n.
Другими словами, вы можете иметь все индексы, обновляющие одну запись, гигантский индекс, а затем вы не можете дать пользователю гарантии того, когда он будет готов (кроме как в конце концов). Или вы можете разделить индекс так, чтобы вы управляли n, таким образом вы можете лучше парализовать и предоставлять результаты в реальном времени для вашего пользователя. Проблема этого подхода заключается в том, что производительность запросов снижается при разбиении на разделы (например, индекс для слова blue теперь существует в нескольких разделах), и в конечном итоге вам необходимо сжимать индексы. Методом разделения MarkLogic и другими базами данных NoSQL является LSM-Tree Cache , управление версиями и сжатие на уровне базы данных называется Multi-Version Concurrency Control .
В MarkLogic есть забавный поворот: они только записывают в память и хранят индексы и документы в буфере (это двойная буферизация, поэтому, когда происходит сброс, вам не нужно ждать, пока новый буфер будет готов). Записи записываются на диск, чтобы в случае сбоя компьютера MarkLogic мог воссоздать индексы и артефакты памяти из индекса. Таким образом, все записывается в память, и когда она заполнена, она записывается на диск. Фактическая часть уплотнения LSM-Tree происходит с артефактами, которые находятся на диске, а не в памяти.
Инвертированные индексы — это очень весело, и они должны лежать в основе любых современных систем баз данных. Они будут через некоторое время ?
Универсальный Индекс
Поэтому с помощью универсального индекса я могу задать любой вопрос, который идет вразрез со словами, и получить очень быстрые ответы на «специальные» запросы без полного сканирования таблицы. Милая. Но если мне нужно что-то, что связано с json, я в беде, инвертированный индекс индексирует только слова.
Именно здесь ребята из MarkLogic изобрели что-то очень крутое под названием Universal Index. Идея состоит в том, что когда вы индексируете слова, вы также индексируете структуру документа. Сначала позвольте мне рассказать вам историю, чтобы вы поняли, почему универсальный индекс работает с родительскими дочерними ассоциациями для хранения структуры.
Как бы вы создали запись в перевернутом индексе, чтобы найти фразу?
Представьте, что я ищу фразу «что-то не так» в документе А
Что-то не так со мной, я кукушка
Если вы используете обычный инвертированный индекс, вы можете найти документ со словом «что-то», документы со словом «неправильно» и документы со словом «с». Но у многих документов, в которых есть все эти термины, предложения не будет. В идеальном мире для этого поиска вы бы группировали термины 3 на 3, чтобы обеспечить этот поиск:
| Срок | Список терминов |
| Здесь что-то не так | |
| что-то не так с | |
| со мной не так | |
| со мной я | |
| я им | |
| я кукушка |
Теперь, если бы я выполнил этот поиск, я бы не нашел ложных срабатываний в индексе, что означает меньшую степень детализации запроса, что обычно приводит к более быстрому запросу. Однако с этим индексом вы не можете искать две словосочетания. Таким образом, по умолчанию в большинстве поисковых индексов индексируют фразы, группируя слова по два.
| Срок | Список терминов |
| Есть что-то | |
| что-то не так | |
| что-то плохо с чем-то | |
| со мной | |
| я им | |
| Я | |
| кукушка |
Если вы найдете предложения, содержащие более двух слов, у вас все еще могут быть ложные срабатывания, но детализация запроса, вероятно, намного лучше и, вероятно, будет работать.
Так зачем все это сейчас? В универсальном указателе вы дополняете инвертированный указатель структурой о документах. Таким образом, хранятся такие вещи, как отношения родитель-потомок Такие вещи, как значение свойства сохраняется. Это увеличивает инвертированный индекс и делает его очень полезным. например, для следующего документа A:
js { "site": { "name": "github" , "description": "social coding done right" } , "owner": "Pedro" }
будет производить следующий индекс:
| Срок | Список терминов | Слово: GitHub | |
| Слово: Социальный | |||
| Слово: Кодирование | |||
| Слово: Готово | |||
| Слово: Право | |||
| Недвижимость: name-> GitHub | |||
| Недвижимость: descrition-> социальное кодирование сделано правильно | |||
| Недвижимость: owner-> Pedro | |||
| Иерархическая: root.site1 | |||
| Иерархическая: root.site1.name | |||
| Иерархическая: root.site1.description | |||
| Иерархическая: root.owner |
И теперь мы можем ответить на очень сложные вопросы, такие как «дайте мне документы, в которых есть слово github, но не термин red, которые принадлежат pedro и называются github».
MarkLogic поднял это на другой уровень, добавив безопасность, коллекции (вид меток gmail) и даже структурируя каталоги, используя инвертированный индекс. Вся прелесть в том, что чем сложнее вы это делаете, тем быстрее возвращается запрос.
Например, если у меня есть 1 миллиард документов, но только 10 из них мои, служба безопасности прямо из индекса увидит, что я вижу только эти 10 документов. Таким образом, максимальное количество операций ввода-вывода, которое я могу сделать, составляет 10, даже в таком большом наборе данных.
Вывод
Есть еще несколько забавных вещей, о которых я мог бы рассказать, но, возможно, в другой статье.
Забавные вещи, такие как, как хранить то, что нравится вашему пользователю, и иметь индексы, которые помогут вам оповещать в масштабе, или регистрировать запросы в вашей системе, или даже использовать карту, чтобы сводить представления запросов в CouchDB.
Не стесняйтесь проверять Inside MarkLogic Paper , она вдавается в бесконечность более подробно, чем этот текст.
Источник: http://writings.nunojob.com/2011/12/Database-Indexes-for-The-Inquisitive-Mind.html