SQLinfo.ru - Все о MySQL Highload++ Junior 2017

Форум пользователей MySQL

Задавайте вопросы, мы ответим

Вы не зашли.

#1 15.04.2017 20:20:07

KenAlcapone
Участник
Зарегистрирован: 15.04.2017
Сообщений: 12

Сортировка таблицы в алфавитном порядке для бинарного поиска

Необходимо сортировать таблицу в алфавитном порядке при добавлении новых значений. Предположим таблица имеет два столбца id и name, мы заносим значения
1) name -> ббб
2) name -> ввв
3) name -> ааа
4) name -> ггг

в таблице должно быть

id  name
0    ааа
1    ббб
2    ввв
3    ггг

То есть когда мы заносим значения в таблицу в столбце id должны меняться индексы в соответствии алфавитного порядка столбца name.

Есть в голове один костыльный вариант, но хотелось бы обойтись без него - заносим новую запись в бд, далее на php в алф. порядке делаем выборку из столбца name одновременно занося данные в массив, далее из этого массива обратно в бд. (в таблице будет примерно 50000 строк и не самый лучший вариант этим грузить php скрипты)

Отредактированно KenAlcapone (15.04.2017 20:25:25)

Неактивен

 

#2 15.04.2017 20:45:49

klow
Активист
Зарегистрирован: 06.12.2014
Сообщений: 158

Re: Сортировка таблицы в алфавитном порядке для бинарного поиска

Колонка id предназначена для идентификация записи в таблице. К сортировке, порядку хранения данных в таблице или их отображению она не имеет отношения.
Вы предложили решение перенумеровать ID (не очень удачное и я бы даже сказал бессмысленное) не сказав, что Вам нужно, какая именно задача стоит перед Вами? Если откроете секрет, думаю, Вам смогут помочь.

Неактивен

 

#3 15.04.2017 21:11:52

KenAlcapone
Участник
Зарегистрирован: 15.04.2017
Сообщений: 12

Re: Сортировка таблицы в алфавитном порядке для бинарного поиска

Мне необходимо сделать алгоритм выборки/сравнения 3000 наименований в секунду из 50000 наименований бд по имени. Линейный поиск тут не уместен, для этого лучше всего подходит бинарный поиск, то есть мы каждый раз не найдя нужные данные будем сокращать поиск в 2 раза, но для этого необходим отсортированный массив в алфавитном порядке, а id нужны для того, что бы можно было обращаться к нужным ячейкам таблицы при поиске.

Предположим у нас есть в таблице 9 значений:

id  name
0     a
1     b
2     c
3     d
4     e
5     f
6     g
7     h
8     i



Нам необходимо найти g, мы берем и делим нашу область поиска на 2 и получаем e, далее сравниваем если e < g, то нам нужно поделить вторую половину на 2 (делим вторую половину на 2 и вот мы уже нашли g), если к примеру в другом случае e > g, то делим первую половину на 2 и так далее пока не найдем нужное значение. (еще бывают исключения, зависит от четности значений)

Отредактированно KenAlcapone (15.04.2017 21:22:33)

Неактивен

 

#4 15.04.2017 21:22:42

klow
Активист
Зарегистрирован: 06.12.2014
Сообщений: 158

Re: Сортировка таблицы в алфавитном порядке для бинарного поиска

Использовать индексы по полю Name не пробовали? Можете получить неожиданный результат в быстродействии. Не думаю, что предложенный Вами алгоритм поиска сможет приблизится к существующему поиску по индексу по скорости. Ожидаю разницу как минимум на порядок. Или, возможно, я не понял Вашу задачу. Но, вроде, стандартная задача для любой СУБД.

Отредактированно klow (15.04.2017 21:24:30)

Неактивен

 

#5 15.04.2017 21:25:39

KenAlcapone
Участник
Зарегистрирован: 15.04.2017
Сообщений: 12

Re: Сортировка таблицы в алфавитном порядке для бинарного поиска

Вот я и не могу понять как сделать индекс в таблице для текстовых значений

Неактивен

 

#6 15.04.2017 21:30:55

klow
Активист
Зарегистрирован: 06.12.2014
Сообщений: 158

Re: Сортировка таблицы в алфавитном порядке для бинарного поиска

Убили наповал.

ALTER TABLE TableName ADD UNIQUE INDEX UK_TableName_Name (Name);
Это если у Вас нет повторов в поле Name.
Если есть повторы то
ALTER TABLE TableName ADD INDEX IDX_TableName_Name (Name);

Неактивен

 

#7 15.04.2017 21:37:36

klow
Активист
Зарегистрирован: 06.12.2014
Сообщений: 158

Re: Сортировка таблицы в алфавитном порядке для бинарного поиска

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

Неактивен

 

#8 15.04.2017 21:42:04

KenAlcapone
Участник
Зарегистрирован: 15.04.2017
Сообщений: 12

Re: Сортировка таблицы в алфавитном порядке для бинарного поиска

Я просто с mysql недавно стал работать smile, не совсем понятно, что это дало, теперь все значения сортируются по алфавиту, но id у них остаются старыми, для бинарного поиска осталось только либо каким нибудь образом обратится к ним как к ячейке массива в том порядке как они стоят, либо присвоить новые id


То есть к примеру нужно из кода обратится к 4 ячейке там где name 'h'
http://i.mcgl.ru/bjKZw5fOpp

Отредактированно KenAlcapone (15.04.2017 21:51:51)

Неактивен

 

#9 15.04.2017 21:59:30

klow
Активист
Зарегистрирован: 06.12.2014
Сообщений: 158

Re: Сортировка таблицы в алфавитном порядке для бинарного поиска

SELECT * FROM TableName t Where t.Name = 'h';

Вместо 'h' подставляете, что Вам нужно.

Отредактированно klow (15.04.2017 22:00:11)

Неактивен

 

#10 15.04.2017 22:07:40

KenAlcapone
Участник
Зарегистрирован: 15.04.2017
Сообщений: 12

Re: Сортировка таблицы в алфавитном порядке для бинарного поиска

Вы меня не правильно поняли, нужно наоборот не по имени, а по номеру ячейки найти, что находится в четвертой, что бы получить 'h', или к нулевой, что бы получить 'a', для бинарного поиска осталось необходимо только получить возможность обращаться к ним по порядковому номеру в котором они выстроились. Что бы можно было их делить на 2 (сокращать уровень поиска на 2)

Отредактированно KenAlcapone (15.04.2017 22:13:29)

Неактивен

 

#11 15.04.2017 22:16:06

klow
Активист
Зарегистрирован: 06.12.2014
Сообщений: 158

Re: Сортировка таблицы в алфавитном порядке для бинарного поиска

Другим словами у Вас есть где-то список номеров и они чему то-то соответствуют но не текущим значениям?так может их и загрузить в БД? Или это случайное число? Возвращаемся туда откуда пришли. Детализации задачи, возможно пример.

Неактивен

 

#12 15.04.2017 22:26:31

KenAlcapone
Участник
Зарегистрирован: 15.04.2017
Сообщений: 12

Re: Сортировка таблицы в алфавитном порядке для бинарного поиска

Приходят наименования товаров по вебсокетам без всяких id, id у меня уже назначается в самой mysql автоинкрементом, теперь на данный момент они сортируются по алфавиту как и было нужно, но после того как они отсортировались по алфавиту у них остаются старые id которые были при записи, а нужно каким либо образом заного их пронумеровать или если их уже mysql пронумеровал обратится к примеру к 5 ячейке и посмотреть, что там лежит (а иначе смысла их упорядочивать по алфавиту не было xD)

Отредактированно KenAlcapone (15.04.2017 22:29:26)

Неактивен

 

#13 15.04.2017 22:46:59

KenAlcapone
Участник
Зарегистрирован: 15.04.2017
Сообщений: 12

Re: Сортировка таблицы в алфавитном порядке для бинарного поиска

ой чет я тут жестко тупанул, можно же ведь использовать select * from test таким образом останавливаться на нужном id smile, спасибо за помощь

Неактивен

 

#14 16.04.2017 08:14:20

klow
Активист
Зарегистрирован: 06.12.2014
Сообщений: 158

Re: Сортировка таблицы в алфавитном порядке для бинарного поиска

KenAlcapone написал:

ой чет я тут жестко тупанул, можно же ведь использовать select * from test таким образом останавливаться на нужном id smile, спасибо за помощь

Ничего не понял. sad
Если нужно найти запись по порядку то предлагаю воспользоваться

SELECT * FROM Test Order By Name Limit RowNum, 1;
Где RowNum - номер записи

Отредактированно klow (16.04.2017 08:15:05)

Неактивен

 

#15 16.04.2017 11:49:38

KenAlcapone
Участник
Зарегистрирован: 15.04.2017
Сообщений: 12

Re: Сортировка таблицы в алфавитном порядке для бинарного поиска

появилась еще одна довольно серьезная проблема, добавление в бд 100 значений занимает 5 сек ($sql="INSERT INTO test1 (id, name) VALUES('','$string')"wink, далее стал экспериментировать, сделал цикл на добавление 10000 записей, зашел в phpmyadmin и увидел, что записи постепенно добавляются, подумал, что из за индексирование mysql не справляется и на сервер огромная нагрузка, но оказалось все иначе, на процессор и оп не было нагрузки даже в 1%, чекал через top на debian.

Если выбрать тип таблицы myISAM или memory, тогда добавление 100 записей занимает 0.008 сек. как и нужно, но в этом случае перестает работать индексирование по полю name.

Отредактированно KenAlcapone (16.04.2017 12:35:34)

Неактивен

 

#16 16.04.2017 19:45:50

klow
Активист
Зарегистрирован: 06.12.2014
Сообщений: 158

Re: Сортировка таблицы в алфавитном порядке для бинарного поиска

Скрипт создания таблицы test1 в студию.
Скрипт добавления значений немного странный, но давайте все по порядку.
Для myISAM индексы тоже великолепно работают. Наверно, проблема в другом.

Неактивен

 

#17 17.04.2017 13:41:52

KenAlcapone
Участник
Зарегистрирован: 15.04.2017
Сообщений: 12

Re: Сортировка таблицы в алфавитном порядке для бинарного поиска

Создавал через интерфейс phpmyadmin -

http://i.mcgl.ru/vJUxPuHPKQ

похоже дело даже не в индексе по полю name, создал новую таблицу example как на скрине и стал заполнять по 100 записей, в итоге это заняло те же 5 сек.


$start = microtime(true);
for ($i = 1; $i <= 100; $i++) {
$length = 8;
$chartypes = "all";
$string = random_string($length, $chartypes);

$sql="INSERT INTO example
  (id, name)
    VALUES('','$string')"
;
  $result = $connection->query($sql);
}
echo ': '.(microtime(true) - $start).' s.';
 

Если добавлять те же 100 записей одним запросом запрос проходит за 0.34 сек

$start = microtime(true);
$query = "INSERT INTO `example`(name) VALUES ";

for ($i = 1; $i <= 100; $i++) {    
  $r = randtext();
  $query .= "('". $r ."')";
 
  if ($i < 100) {
    $query .= ", ";
  }
}
$result = $connection->query($query);
echo ': '.(microtime(true) - $start).' s.';



Если изменить тип таблицы на myISAM, тогда те же 100 записей при добавлении по одной заносятся всего за 0.01 сек вместо 5, но при добавлении индекса через - ALTER TABLE example ADD INDEX IDX_example_name (name); он не работает с myISAM и Memory, он успешно добавляется но свои действия не выполняет по сортировке, если сменить тип на innoDB, тогда начинает работать

Отредактированно KenAlcapone (17.04.2017 14:29:28)

Неактивен

 

#18 17.04.2017 16:22:29

klow
Активист
Зарегистрирован: 06.12.2014
Сообщений: 158

Re: Сортировка таблицы в алфавитном порядке для бинарного поиска

Я не работаю с phpmyadmin, но думаю это вкладка SQL. Приведите ее содержимое. 
Судя по рисунку индексов у Вас нет.
Для Вашего случая таблица, скорее всего, должна быть такая:

CREATE TABLE example (
  ID int(11) NOT NULL AUTO_INCREMENT,
  Name varchar(33) DEFAULT NULL,
  PRIMARY KEY (ID),
  UNIQUE INDEX UK_example (Name)
)
ENGINE = INNODB;

Неактивен

 

#19 17.04.2017 17:05:06

KenAlcapone
Участник
Зарегистрирован: 15.04.2017
Сообщений: 12

Re: Сортировка таблицы в алфавитном порядке для бинарного поиска

Нашел в чем была причина, логи записывались напрямую в пзу, исправил на innodb_flush_log_at_trx_commit = 2, теперь 100 insert'ов занимают по времени 0,22сек вместо 5сек smile, только вот все же не понятно почему не работают индексы в MYISAM и MEMORY таблицах.

К примеру вот так с myisam индексы уже не работают -

CREATE TABLE example (
  ID int(11) NOT NULL AUTO_INCREMENT,
  Name varchar(33) DEFAULT NULL,
  PRIMARY KEY (ID),
  UNIQUE INDEX UK_example (Name)
)
ENGINE = MYISAM;

Неактивен

 

#20 17.04.2017 17:28:29

vasya
Архат
MySQL Authorized Developer
Откуда: Орел
Зарегистрирован: 07.03.2007
Сообщений: 5126

Re: Сортировка таблицы в алфавитном порядке для бинарного поиска

опишите подробней, какой смысл вы вкладываете в "индексы уже не работают"

Неактивен

 

#21 17.04.2017 17:47:51

KenAlcapone
Участник
Зарегистрирован: 15.04.2017
Сообщений: 12

Re: Сортировка таблицы в алфавитном порядке для бинарного поиска

Хотел сказать, что не работает сортировка по индексу вот отличия

http://i.mcgl.ru/uU0SJ8nYCN

http://i.mcgl.ru/G2kR5gljUy

Неактивен

 

#22 17.04.2017 17:53:29

vasya
Архат
MySQL Authorized Developer
Откуда: Орел
Зарегистрирован: 07.03.2007
Сообщений: 5126

Re: Сортировка таблицы в алфавитном порядке для бинарного поиска

а где у вас в запросе сортировка?

Неактивен

 

#23 17.04.2017 17:57:32

vasya
Архат
MySQL Authorized Developer
Откуда: Орел
Зарегистрирован: 07.03.2007
Сообщений: 5126

Re: Сортировка таблицы в алфавитном порядке для бинарного поиска

если вы не указываете order by, то можете получить результат в непредсказуемом порядке
и в примере с тем же innodb, завтра при ином положении звезд результат может быть другой.

Неактивен

 

#24 17.04.2017 18:14:43

KenAlcapone
Участник
Зарегистрирован: 15.04.2017
Сообщений: 12

Re: Сортировка таблицы в алфавитном порядке для бинарного поиска

Точно они в обоих случаях находятся в алфавитном порядке по полю name, их просто по разному выводит

SELECT * FROM `example2`
,  проверил через InnoDB и MyISAM один и тот же правильный результат smile,
SELECT * FROM example2 Order By name Limit 1, 1
result = !%(@JqD)

Все равно довольно странно почему такое отличие в innoDB и в myISAM при одинаковом запросе
SELECT * FROM `example2

Отредактированно KenAlcapone (17.04.2017 18:15:14)

Неактивен

 

#25 17.04.2017 18:30:06

vasya
Архат
MySQL Authorized Developer
Откуда: Орел
Зарегистрирован: 07.03.2007
Сообщений: 5126

Re: Сортировка таблицы в алфавитном порядке для бинарного поиска

KenAlcapone написал:

Точно они в обоих случаях находятся в алфавитном порядке по полю name, их просто по разному выводит

если под они вы подразумеваете порядок хранения строк на диске, то то не так
бд это просто куча и такое понятие как первая или последняя строка в ней отсутствует
и если вы не указываете order by, то результат непредсказуемый
что касается отличия в поведение InnoDB и в MyISAM, то они по разному хранят данные внутри себя

Неактивен

 

Board footer

Работает на PunBB
© Copyright 2002–2008 Rickard Andersson