Почему индексы БД используют сбалансированные деревья, а не хеш-таблицы?
== сравнивает ссылки на объекты.
.equals() сравнивает значения String.
Иногда == дает иллюзии сравнения значений String, как в следующих случаях:
String a="Test";
String b="Test";
if(a==b) ===> true
Это связано с тем, что при создании любого строкового литерала JVM сначала ищет этот литерал в пуле строк, и если он найдет совпадение, эта же ссылка будет передана новой String. Из-за этого получаем:
(a == b) ===> true
String Pool
b -----------------> "test" <-----------------a
Однако == не выполняется в следующем случае:
String a="test";
String b=new String("test");
if (a==b) ===> false
В этом случае для new String("test") оператор new String будет создан в куче, и эта ссылка будет указана на b, поэтому b будет дана ссылка на кучу, а не на String pool.
Теперь a указывает на String в пуле String, а b указывает на String в куче. Из-за этого мы получаем:
, если (a == b) ===> false.
String Pool
"test" <-------------------- a
Heap
"test" <-------------------- b
Пока .equals() всегда сравнивает значение String, поэтому дает true в обоих случаях:
String a="Test";
String b="Test";
if(a.equals(b)) ===> true
String a="test";
String b=new String("test");
if(a.equals(b)) ===> true
Таким образом, использование .equals() всегда лучше.
6 ответов
Размер, b-деревья начинаются с малого, имеют идеальную форму и постепенно растут до огромных размеров. Хэши имеют фиксированный размер, который может быть слишком большим (10 000 сегментов для 1000 записей) или слишком маленьким (10 000 сегментов для 1 000 000 000 записей) для того объема данных, который у вас есть.
Хеш-таблицы не дают никаких преимуществ в этом случае:
SELECT * FROM MyTable WHERE Val BETWEEN 10000 AND 12000
Одним из распространенных действий с данными является их сортировка или поиск данных в диапазоне - дерево будет содержать данные по порядку, а хеш-таблица полезна только для поиска по строке и понятия не имеет, какая будет следующая строка.
Таким образом, хеш-таблицы не подходят для этого общего случая, благодаря этому ответу
SELECT * FROM MyTable WHERE Val BETWEEN 10000 AND 12000
или
SELECT * FROM MyTable ORDER BY x
Очевидно, есть случаи, когда хеш-таблицы лучше, но лучше сначала рассмотрим основные дела.
Базы данных обычно используют деревья B + (особый вид дерева), поскольку они имеют улучшенные свойства доступа к диску - каждый узел может быть размером с блок файловой системы. Как можно меньше операций чтения с диска имеет большее влияние на скорость, поскольку сравнительно мало времени тратится на поиск указателей в дереве или на хеширование.
Хазинг хорош, когда данные не увеличиваются, точнее говоря, когда N / n является постоянным. где N = количество элементов и n = хэш-слоты.
Если это не так, хеширование не дает хорошего прироста производительности.
В базе данных, скорее всего, данные будут увеличиваться значительным темпом, поэтому использование хеш-функции не очень хорошая идея.
и да, сортировка тоже есть ...
«В базе данных, скорее всего, данные будут увеличиваться со значительной скоростью, поэтому использование хэша - не лучшая идея».
Это преувеличение проблемы. Да, размер хеш-пространств должен быть фиксированным (решения по модулю, а также расширяемое хеширование), и да, их размером нужно управлять, и да, кто-то должен выполнять эту работу.
Тем не менее, производительность возрастает, если вы используете физическое местоположение на основе хеша. в полном объеме, огромны.