Хеш-таблица, массив, индекс

https://en.wikipedia.org/wiki/Concurrent_hash_table

Параллельная хеш-таблица или параллельная хеш-карта или многопоточная хэш-таблица — это реализация хеш-таблиц, позволяющая параллельный доступ нескольким потокам с использованием хеш-функции.^[1][2]

Параллельные хеш-таблицы представляют собой ключевую параллельную структуру данных для использования в параллельных вычислениях, которая позволяет нескольким потокам более эффективно взаимодействовать при вычислениях с общими данными.^[1]

 https://ru.m.wikipedia.org/wiki/Хеш-таблица

Хеш-табли́ца — структура данных, реализующая интерфейс ассоциативного массива, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию удаления и операцию поиска пары по ключу.

https://ru.m.wikipedia.org/wiki/Ассоциативный_массив

Ассоциативный массив — абстрактный тип данных (интерфейс к хранилищу данных), позволяющий хранить пары вида «(ключ, значение)» и поддерживающий операции добавления пары, а также поиска и удаления пары по ключу:

• INSERT(ключ, значение)
• FIND(ключ)
• REMOVE(ключ)

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

В паре ${\displaystyle (k,v)}$ значение ${\displaystyle v}$ называется значением, ассоциированным с ключом ${\displaystyle k}$. Где ${\displaystyle k}$ — это key, a ${\displaystyle v}$ — value. Семантика и названия вышеупомянутых операций в разных реализациях ассоциативного массива могут отличаться.

Операция FIND(ключ) возвращает значение, ассоциированное с заданным ключом, или некоторый специальный объект UNDEF, означающий, что значения, ассоциированного с заданным ключом, нет. Две другие операции ничего не возвращают (за исключением, возможно, информации о том, успешно ли была выполнена данная операция).

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

Примером ассоциативного массива является телефонный справочник: значением в данном случае является совокупность «Ф. И. О. + адрес», а ключом — номер телефона, один номер телефона имеет одного владельца, но один человек может иметь несколько номеров.

Три основных операции часто дополняются другими, наиболее популярные расширения:

• CLEAR — удалить все записи,
• EACH — «пробежаться» по всем хранимым парам,
• MIN — найти пару с минимальным значением ключа,
• MAX — найти пару с максимальным значением ключа.

В последних двух случаях необходимо, чтобы на ключах была определена операция сравнения.

Реализации ассоциативного массиваправитьСуществует множество различных реализаций ассоциативного массива.

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

Наиболее популярны реализации, основанные на различных деревьях поиска. 

У каждой реализации есть свои достоинства и недостатки. Важно, чтобы все три операции выполнялись как в среднем, так и в худшем случае за время ${\displaystyle O(\log n)}$, где ${\displaystyle n}$ — текущее количество хранимых пар. Для сбалансированных деревьев поиска (в том числе для красно-чёрных деревьев) это условие выполнено.

В реализациях, основанных на хеш-таблицах, среднее время оценивается как ${\displaystyle O(1)}$, что лучше, чем в реализациях, основанных на деревьях поиска. Но при этом не гарантируется высокая скорость выполнения отдельной операции: время операции INSERT в худшем случае оценивается как ${\displaystyle O(n)}$. Операция INSERT выполняется долго, когда коэффициент заполнения становится высоким и необходимо перестроить индекс хеш-таблицы.

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

https://ru.m.wikipedia.org/wiki/Двоичный_поиск

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

Поиск элемента в отсортированном массиве

1. Определение значения элемента в середине структуры данных. Полученное значение сравнивается с ключом.
2. Если ключ меньше значения середины, то поиск осуществляется в первой половине элементов, иначе — во второй.
3. Поиск сводится к тому, что вновь определяется значение серединного элемента в выбранной половине и сравнивается с ключом.
4. Процесс продолжается до тех пор, пока не будет найден элемент со значением ключа или не станет пустым интервал для поиска.

https://ru.m.wikipedia.org/wiki/Массив_(тип_данных)

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

Размерность массива — это количество индексов, необходимое для однозначной адресации элемента в рамках массива^[1]. По количеству используемых индексов массивы делятся на одномерные, двумерные, трёхмерные и т. д.

Форма или структура массива — сведения о количестве размерностей и размере (протяжённости) массива по каждой из размерностей^[2]; может быть представлена одномерным массивом^[3].

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

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

Индексы

Индекс в базе данных — это дополнительная структура данных, которая создаётся наряду с данными в таблице. 1 Она сопоставляет значения в одном или нескольких столбцах таблицы с соответствующими местоположениями на физическом накопителе, что позволяет базе данных быстро находить строки по конкретному запросу без необходимости сканирования всей таблицы. 2

Таким образом, роль индексов состоит в том, чтобы облегчить поиск подмножества строк и столбцов таблицы без необходимости сканировать каждую строку в таблице. 3

Главная задача индексов — ускорить процесс извлечения данных и тем самым повысить производительность запросов. 1

Например, кластеризованный индекс определяет порядок, в котором данные хранятся на странице (физически) и в таблице (неявно). 1

1. wiki.merionet.ru

   1
2. habr.com

   2
3. sql-academy.org

   3

https://sql-academy.org/ru/guide/indexes

Индексы в SQL

Когда вы добавляете в таблицу новую строку, СУБД размещает эти данные не оптимально. Например, если вы добавляете строку в таблицу Users, СУБД не размещает строки в числовом порядке значений столбца id или в алфавитном порядке значений столбца last_name. Вместо этого он просто помещает данные в следующее доступное место в файле (СУБД поддерживает список свободных мест для каждой таблицы).

Это приводит к тому, что для выполнения запроса типа:

MySQL
SELECT email FROM Users WHERE email LIKE 'l%';

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

Индексы функционируют как предметные указатели в книге 📖, позволяя быстро находить информацию без прочтения всего текста. Они представляют собой специальные таблицы, строки которых, в отличие от обычных таблиц данных, расположены в строго определённом порядке. Но вместо того, чтобы содержать все данные о некоторой записи, индекс содержит только столбец (или столбцы), используемый, чтобы найти строки в таблице данных, вместе с информацией, описывающей, где физически расположена эта строка. Таким образом, роль индексов состоит в том, чтобы облегчить поиск подмножества строк и столбцов таблицы без необходимости сканировать каждую строку в таблице.