5 заметок с тегом

структуры данных

Небольшая заметка об индексах в ms sql

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

Что из себя представляет индекс?

Внутри сервера они представлены в виде B-tree, где B означает сбалансированное, а не бинарное дерево.

Например мы хотим найти запись с Id = 2581.
Начиная с корня, выполняется поиск наименьшего значения ключа, большего или равного требуемому. Так мы найдем узел 18316, потом спустимся в узел 9031 и там мы увидим что есть прямая ссылка на лежащие данные по ключу 2581, после чего осуществляем вычитку данных.

Кластерный индекс

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

Не кластерный индекс

Структура такая же как и кластерного индекса, но с двумя отличиями:

  1. Не изменяет физическое упорядочивание данных.
  2. Страницы индекса состоят из ключа индекса и ссылки на строку.

SQL Server использует индекс для нахождения записей, совпадающих с условиями запроса.

Составной ключ в индексе

SQL Server позволяет создавать индексы по нескольким колонкам. Но в таком случае у нас появляется ограничение. Длинна составного ключа не должна быть больше 900 байт. Но бывают исключения, например у нас есть две колонки, каждая из которых длинной в 500 байт. Сервер создаст индекс, в случае если нет данных, которые будут превышать длину в 900 байт.

Также стоит помнить что индексы типа (Col1, Col2) и (Col2, Col1) разные.

Уникальные индексы

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

Статьи, которые советую почитать чтобы глубже разобраться в теме

  1. Очень хорошая статья о всех типах индексов, когда их стоит создавать и как использовать
  2. Индексы. Теоретические основы.
 Нет комментариев    82   2 мес   sql   программирование   структуры данных

GIN индекс

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

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

Хорошая аналогия для этого метода — алфавитный указатель в конце книги, где для каждого термина приведен список страниц, где этот термин упоминается.

 Нет комментариев    51   3 мес   программирование   структуры данных

Алгоритм поиска Ли

Алгоритм поиска пути в планарном графе. Зачастую используется в схемотехнике и в играх (стратегиях) для поиска кратчайшего пути.

Алгоритм состоит из 3 шагов:

  1. Инициализация
  2. Распространение волны
  3. Восстановление пути

Также есть 2 способа поиска пути: ортогональный и ортогонально-диагональный. Ниже на скриншотах можно увидеть работу этих двух способов.

Ортогональный поиск.
Ортогонально-диагональный поиск.

Псевдокод

Взято из Википедии.

Инициализация

Пометить стартовую ячейку 
d := 0

Распространение волны

ЦИКЛ
  ДЛЯ каждой ячейки loc, помеченной числом d
    пометить все соседние свободные непомеченные ячейки числом d + 1
  КЦ
  d := d + 1
ПОКА (финишная ячейка не помечена) И (есть возможность распространения волны)

Восстановление пути

ЕСЛИ финишная ячейка помечена
ТО
  перейти в финишную ячейку
  ЦИКЛ
    выбрать среди соседних ячейку, помеченную числом на 1 меньше числа в текущей ячейке
    перейти в выбранную ячейку и добавить её к пути
  ПОКА текущая ячейка — не стартовая
  ВОЗВРАТ путь найден
ИНАЧЕ
  ВОЗВРАТ путь не найден

Пример кода, который реализует алгоритм и выводит на экран путь (C#).

 Нет комментариев    75   3 мес   c#   алгоритмы   программирование   структуры данных

Хеш-таблица

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

Есть два основных способа реализации хеш-таблицы:

  1. Метода цепочек — данные с одинаковым хешем обьединяються в список.
  2. Метод открытой адресации — если при добавлении данных ячейка занята, то переходим к следующей, до тех пор пока не найдем свободную.

В .NET уже существует готовая реализация этой структуры: System.Collections.HasTable. Но с появлением обобщенных коллекций стал устаревшим. На его место пришел словарь — Dictionary. Так как в базовом объекте есть 2 метода Equal и GetHashCode мы можем в качестве ключа словаря использовать любой тип данных.

 Нет комментариев    73   3 мес   .net   программирование   структуры данных

Структуры данных: связанные списки

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

Наиболее используемые типы списков:

  1. Односвязный список
+-------+------+    +-------+-------+ 
| Hello |  *---+--->| world | null  +
+-------+------+    +-------+-------+
  1. Двусвязный список
+----------+---------+       +----------+----------+ 
|          |     *---|------>|          |          |
|  Hello   |         |       |          |  world   |
|          |         |<------|---*      |          |
+----------+---------+       +----------+----------+
  1. Кольцевой список
.        +-------<----------<--------------<--------+
         |                                          |
+-----+--+---+    +-----+------+    +-----+-----+   |
| 12  |  *---+--->| 15  |   *--+--->| 25  |  *--+---+
+-----+------+    +-----+------+    +-----+-----+



Быстродействие

  • Добавляет элемент в конец/начало списка — O(1)
  • Удаляет первый элемент списка со значением, равным переданному — O(n)
  • Поиск элемента — O(n)
  • Копирование а массив — O(n)
  • Получить количество — O(1)

Преимущества

  1. Элементы могут быть удалены или добавлены из середины списка
  2. Нет необходимости объявлять разvер списка при инициализации
  3. Эффективное удаление и добавление элементов

Недостатки

  1. Связанные списки не имеют возможности произвольного доступа к элементам — т. е. нет возможности получить элемент внутри списка, без того что бы пройтись по всем элементам до него.
  2. Для работы списков требуется динамическое выделение памяти, что может привести к утечкам памяти.

Ссылки

  1. https://metanit.com/sharp/algoritm/2.1.php
  2. https://rtfm.co.ua/c-svyazannye-spiski/
  3. https://ru.wikipedia.org/wiki/Связный_список
  4. https://tproger.ru/translations/linked-list-for-beginners/
  5. https://medium.com/outco/reversing-a-linked-list-easy-as-1-2-3-560fbffe2088
 Нет комментариев    86   5 мес   программирование   структуры данных