Резюме

Во время интервью, когда мы обменивались вопросами об индексе mysql, я обнаружил, что некоторые люди могут отличить дерево B+ от дерева B, сбалансированного двоичного дерева, но не могут отличить дерево B+ от хэш-индекса. На первый взгляд известно, что это заучивание наизусть, без понимания природы индекса. Эта статья направлена на анализ принципа, лежащего в основе этого, добро пожаловать, чтобы оставить сообщение для обсуждения

проблема

Если вы запутались или немного понимаете следующие вопросы, пожалуйста, продолжайте читать, я уверен, что эта статья определенно вам поможет.

Как реализован индекс mysql
В чем разница между структурой индекса mysql B+ и хешем. К какому сценарию относится?
Существуют ли другие реализации индексации базы данных?
Как реализована таблица переходов Redis
В чем разница между таблицей переходов и деревом B+ и деревом LSM?

Разобрать

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

Когда вы думаете о проблеме с этой точки зрения, знаете ли вы разницу между индексом дерева B+ и хэш-индексом?

Поиск проблем в наборах данных

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

Какие методы поиска необходимо поддерживать, одноключевой/многоключевой/диапазонный поиск,
Вставить/удалить эффективность
Эффективность поиска (т.е. временная сложность)
Размер хранилища (сложность пространства)

Давайте рассмотрим несколько часто используемых поисковых структур.

hash

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

Дерево B+ построено на основе сбалансированного бинарного дерева, почему мы не изучили структуру дерева B+ и таблицу пропусков на уроке алгоритма? Поскольку все они получены из инженерной практики, на основе теории были достигнуты компромиссы.

Дерево B+ — это, прежде всего, упорядоченная структура.Чтобы высота дерева не была слишком большой и не влияла на эффективность поиска, листовой узел хранит не отдельные данные, а страницу данных, что повышает эффективность поиска. , а для лучшей поддержки запросов диапазона, избыточных данных B+ дерева неконечных узлов в конечных узлах, чтобы поддерживать перелистывание страниц, конечные узлы соединены указателями.

пропустить стол

Список пропуска расширяется на основе связанного списка, чтобы реализовать структуру данных отсортированного множества Redis. level0: для хранения исходных данных, это упорядоченный связанный список, каждый узел находится в цепочке level0+: Узлы соединены последовательно через указатели, которые являются подмножеством исходных данных.Чем выше уровень, тем меньше данных соединено последовательно, что может значительно повысить эффективность поиска.

Суммировать

структура данных	Принцип реализации	ключевой метод запроса	Найдите эффективность	размер хранилища	Эффективность вставки и удаления
Hash	хеш-таблица	Поддержка одного ключа	близко к O (1)	Небольшой, нет дополнительного хранилища, кроме данных	O(1)
В+ дерево	Сбалансированное бинарное дерево расширено	Один ключ, диапазон, нумерация страниц	O(Log(n)	В дополнение к данным есть левый и правый указатели, а также указатели конечных узлов.	O(Log(n), структуру дерева нужно скорректировать, алгоритм усложняется
пропустить стол	расширение упорядоченного связанного списка	один ключ, пагинация	O(Log(n)	В дополнение к данным указателей больше, но указатель каждого узла меньше	O (Log (n), работающий только со связанными списками, алгоритм относительно прост

Если вас интересует структура LSM, вы можете посмотреть на неекассандра против монго (1) механизм хранения

Полезный лайк, спасибо

Ссылаться на

Блог woohoo.cn на.com/Elliott-SU-…