221VOLT написав:iovchynnikov написав:221VOLT написав:запитання - індекс по якому стовпчику буде швидшим і чому?
А які запити ви найбільше будете робити?
Якщо ви будете робити тільки SELECT hash FROM table WHERE id=** то хеш буде швидшим (O(1) проти O(log)). В усіх інших випадках (особливо будь-які порівняльні операції >, <, between), дерево буде швидшим, де дерево виконує операції за O(log) а пошук по хеш таблиці перетворюється/майже перетворюється на full table scan. Саме тому дерево є індексом за замовчуванням, а у багатьох db - єдиний варіянт.
Поза тим, постгрес у зв'язку з реалізацією може перебудовувати hash індекс. Так, наприклад, postgress перебудує повністю hash індекси після крешу бази, або проблемах з записом даних (https://www.postgresql.org/docs/9.1/sta … types.html).
Для md5 найкращій тип це char[32].
так, запит саме такий (WHERE id=** , перепрошую, затупив я - відразу не написав сам запит)
чесно - я не зрозумів, чому хеш буде швидшим,
хоча трошки і читав про btree (якби розумів - запитання не виникло би))
буду вдячний за будь-який маленький приклад - на прикладі швидше доходить
(хочеться нарешті зрозуміти цю відмінність, закрити для себе це запитання)
Особливого розуміння тут не треба, це - особливості самих структур даних: hashtable i b-tree.
Най маємо 2 індекси: hashIndex(id, md5), btreeIndex(id, md5)
hashIndex зберігає дані у постаті таблиці:
------------------------------------------
| hash(id) | List<md5> ("бакет") |
------------------------------------------
Наприклад, якщо таку таблицю
------------------------------
| 1 | 1312dasdas131sad |
| 2 | vcxvxvxcvxcvxcsaad |
| 3 | asasasasasasasasa |
| 4 | 111zzzxxxccc55555 |
| 5 | pppppppppppaaaaa |
------------------------------
проіндексовані стовпчики можуть виглядати у масиві так:
----------------------------------------------------------
| 123sc | [1, 1312dasdas131sad], [2, vcxvxvxcvxcvxcsaad]
| 5serc | [3, asasasasasasasasa]
| 632x | [4, 111zzzxxxccc55555]
| 112x | [5, pppppppppppaaaaa]
-------------------------------------------------------------
array[123sc] = list([1, 1312dasdas131sad], [2, vcxvxvxcvxcvxcsaad])
array[5serc] = list([3, asasasasasasasasa])
Алгоритм створення хеш таблиці такий:
1) Беремо якийсь_алгоритм_хешування і застосовуємо його до ключа (1 стовпчик). Отримане значення - ключ у хеш таблиці.
2) Дописуємо у відповідний бакет відповідне до ключа значення (2 стовпчик).
Чому у бакеті може бути кілька значень? Тому що якийсь_алгоритм_хешування не дає 100% унікальний id бакета, тож 2 різних значення у 1 стовпчику можуть дати 1 й той самий індекс. Ось тому у нашій таблиці 1312dasdas131sad,vcxvxvxcvxcvxcsaad відповідають різні індексі, а у хештаблиці вони знаходяться у одному бакеті під 1 індексом.
Ну і тепер чому це where id = ** працює швидше.
Уявіть таблицю у базі у вигляді зв'язаного списку. Пошук по такій базі - ітерація від елементу до елементу і перевірка чи індекси співпадають. ~ O(n)
Якщо ми створюємо хеш індекс, пошук вже буде відбуватися у хештаблиці, яка зберігається у вигляді масиву, доступ до елементів якого за індексом є дуже швидкою операцію (тому що кожній комірці масиву відповідає однозначний адрес у пам'яті). Залишилося лише:
..where id = 1
1) якийсь_алгоритм_хешування(1) = 123sc
2) hastableArray[123sc] = list([1, 1312dasdas131sad], [2, vcxvxvxcvxcvxcsaad])
3) findValueInBucketByKey(1, list([1, 1312dasdas131sad], [2, vcxvxvxcvxcvxcsaad])) = 1312dasdas131sad
Тобто у порівнянні до пошуку за усією таблицею, використовуючи індекс можна "зрізати" одразу пошук до 1-5 значень.
Натомість дерево будує...збалансоване дерево, яке треба обходити:
Звичайно, тупо він не обходить, а звіряється зі значенням ключів, де праве значення, більше лівого (чи навпаки) і вирішує у яку сторону піти, доки не знайде потрібне. І ця операція може буде у більшості випадках повільніша.
Але як я і говорив, хештейбл не пристосований до порівняльних операції, тому що хеши не порівняєш і треба робити повний пошук, а у дереві можна так само порівнювати з вершинами графу.
Сподіваюся хоч щось зрозуміло з цього))
