Как стать автором
Обновить

Обзор типов индексов Oracle, MySQL, PostgreSQL, MS SQL

SQL *
В одном из комментариев здесь была просьба рассказать подробнее об индексах, и так как, в рунете практически нет сводных данных о поддерживаемых индексах различных СУБД, в данном обзоре я рассмотрю, какие типы индексов поддерживаются в наиболее популярных СУБД
Взглянем?
Всего голосов 99: ↑96 и ↓3 +93
Просмотры 158K
Комментарии 41

B-tree

Алгоритмы *
Из песочницы

Введение


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

Основные операции в деревьях выполняются за время пропорциональное его высоте. Сбалансированные деревья минимизируют свою высоту (к примеру, высота бинарного сбалансированного дерева с n узлами равна log n). Большинство знакомо с такими сбалансированными деревьями, как «красно-черное дерево», «AVL-дерево», «Декартово дерево», поэтому не будем углубляться.

В чем же проблема этих стандартных деревьев поиска? Рассмотрим огромную базу данных, представленную в виде одного из упомянутых деревьев. Очевидно, что мы не можем хранить всё это дерево в оперативной памяти => в ней храним лишь часть информации, остальное же хранится на стороннем носителе (допустим, на жестком диске, скорость доступа к которому гораздо медленнее). Такие деревья как красно-черное или Декартово будут требовать от нас log n обращений к стороннему носителю. При больших n это очень много. Как раз эту проблему и призваны решить B-деревья!

B-деревья также представляют собой сбалансированные деревья, поэтому время выполнения стандартных операций в них пропорционально высоте. Но, в отличие от остальных деревьев, они созданы специально для эффективной работы с дисковой памятью (в предыдущем примере – сторонним носителем), а точнее — они минимизируют обращения типа ввода-вывода.
Читать дальше →
Всего голосов 82: ↑75 и ↓7 +68
Просмотры 168K
Комментарии 32

NetworkX для удобной работы с сетевыми структурами

Python *

Рассматривается библиотека NetworkX предназначенная для создания, манипуляции и изучения структуры, динамики и функционирования сложных сетевых структур.
Рассмотрены основы использования библиотеки в качестве инструмента обучения, прикладного программирования или научных исследований.
Основой для описания библиотеки служат официальные материалы с сайта.
Рассмотрена версия библиотеки 1.5.
Читать дальше →
Всего голосов 59: ↑56 и ↓3 +53
Просмотры 74K
Комментарии 35

С++ библиотека от Google с контейнерами map и set на B-деревьях

Программирование *C++ *Алгоритмы *
Один из сотрудников Google в 20% свободного времени разработал и выложил под свободной лицензией библиотеку cpp-btree (С++ B-Tree), которая содержит контейнеры, работающие как map, set, multimap и multiset из стандартной библиотеки шаблонов (STL).

Разница в том, что контейнеры в STL реализованы на красно-чёрных деревьях, а аналогичные контейнеры cpp-btree — на B-деревьях. При этом в определённых ситуациях достигается существенный выигрыш в использовании памяти (на элементах маленького размера) и в производительности (на больших размерах контейнера).

B-деревья известны как инструмент для работы с дисковой памятью: базами данных и файловой системой. Но те же свойства, которые дают выигрыш там, позволяют эффективнее использовать и оперативную память. Каждый узел красно-чёрного дерева содержит один элемент, требует три указателя плюс по биту информации на элемент для сбалансированности. Для сравнения, контейнеры на B-деревьях хранят несколько элементов на узел, поэтому уменьшают оверхед указателей и экономят значительное количество памяти.
Читать дальше →
Всего голосов 82: ↑77 и ↓5 +72
Просмотры 29K
Комментарии 34

Файловое строение SQLite

SQLite *
Перевод
В данном посте база SQLite будет рассмотрена в разрезе, вы можете найти информацию о строении файла базы данных, о представлении данных в памяти, а также информацию о структуре и файловом представлении В – дерева.
Читать дальше →
Всего голосов 29: ↑23 и ↓6 +17
Просмотры 32K
Комментарии 21

Вопросы про индексы, которые вам не надо будет задавать

Разработка веб-сайтов *SQL *Microsoft SQL Server *
Tutorial


После ответов на 14 вопросов об индексах, которые вы стеснялись задать, у меня возникло гораздо больше комментариев, уточнений и исправлений. Скомпилировать из всего этого статью выглядело затеей с минимумом пользы. И это заставило меня призадумался, а почему вообще мы должны «стесняться задавать» подобные вопросы? Стыдно не знать? А есть ли способ разобраться, не вгоняя себя в краску? Есть. Причем он избавит от многочисленных неточностей, которыми изобилуют многие «ответы». Вы будете чувствовать буквально каждый байт вашей базы кончиками своих пальцев.

Для этого, я предлагаю «поднять капот» у SQL Server и окунуться в сладостный мир шестнадцатеричных дампов. Может статься, что внутри все гораздо проще, чем вам казалось.
Читать дальше →
Всего голосов 36: ↑34 и ↓2 +32
Просмотры 45K
Комментарии 9

Сбалансированное дерево поиска B-tree (t=2)

C++ *Алгоритмы *
Recovery mode
Из песочницы

Введение и постановка задачи


На 3-м курсе обучения в своем университете передо мной встала задача реализовать B-дерево, содержащее уникальные ключи, упорядоченное по возрастанию (со степенью t=2) на языке c++ (с возможностью добавления, удаления, поиска элементов и соответственно, перестройкой дерева).

Перечитав несколько статей на Хабре (например, B-tree, 2-3-дерево. Наивная реализация и другие), казалось бы, все было ясно. Только теоретически, а не практически. Но и с этими трудностями мне удалось справиться. Цель моего поста — поделиться полученным опытом с пользователями.
Читать дальше →
Всего голосов 18: ↑7 и ↓11 -4
Просмотры 26K
Комментарии 32

Квинтет как базовая сущность для описания предметной области

Блог компании Neoflex IT-стандарты *Функциональное программирование *Хранение данных *Будущее здесь
Recovery mode
Квинтет — это способ записать атомарные фрагменты данных с указанием их роли в нашей жизни. Квинтетами можно описать любые данные, при этом каждый из них содержит исчерпывающую информацию о себе и о связях с другими квинтетами. Он представляет термины предметной области, независимо от используемой платформы. Его задача — упростить хранение данных и улучшить наглядность их представления.



Я расскажу о новом подходе к хранению и обработке информации и поделюсь мыслями о создании платформы разработки в этой новой парадигме.
Взглянуть по-новому на известные вещи
Всего голосов 17: ↑8 и ↓9 -1
Просмотры 4.9K
Комментарии 60

Структура данных B-дерево

Блог компании OTUS Алгоритмы *
Перевод
Всем привет! Мы запустили новый набор на курс «Алгоритмы для разработчиков» и сегодня хотим поделиться интересным переводом, подготовленным для студентов данного курса.



В деревьях поиска, таких как двоичное дерево поиска, AVL дерево, красно-чёрное дерево и т.п. каждый узел содержит только одно значение (ключ) и максимум двое потомков. Однако есть особый тип дерева поиска, который называется B-дерево (произносится как Би-дерево). В нем узел содержит более одного значения (ключа) и более двух потомков. B-дерево было разработано в 1972 году Байером и МакКрейтом и называлось Сбалансированное по высоте дерево поиска порядка m (Height Balanced m-way Search Tree). Свое современное название B-дерево получило позже.
Читать дальше →
Всего голосов 19: ↑13 и ↓6 +7
Просмотры 30K
Комментарии 5

Как и почему в InnoDB появились индексы на основе В-дерева

Блог компании Ситимобил MySQL *
🔥 Технотекст 2020
Всем хорошо известно, что индексы на основе структуры данных В-дерево помогают нам быстрее читать и находить записи в таблицах. В сети можно найти огромное количество информации по этому поводу, но я постараюсь показать, с какими проблемами нам пришлось бы столкнуться без использования индексов на основе В-дерева, и почему выбрали эту структуру данных. И в качестве примера я возьму подсистему хранения InnoDB из MySQL.

Чтобы разобраться, как появились индексы на основе В-дерева, давайте представим мир без них и попробуем решить типовую задачу. Попутно обсудим проблемы, с которыми столкнемся, и способы их решения.

image
Читать дальше →
Всего голосов 13: ↑12 и ↓1 +11
Просмотры 3.9K
Комментарии 7