Связанный список в SQL

Question

Как лучше всего хранить связанный список в базе данных MySQL, чтобы вставки были простыми (т.вам не придется каждый раз переиндексировать кучу вещей) и так, чтобы список можно было легко расставить по порядку.

Answer 1

Сохраните целочисленный столбец в своей таблице под названием «позиция».Запишите 0 для первого элемента вашего списка, 1 для второго элемента и т. д.Проиндексируйте этот столбец в своей базе данных, и когда вы захотите извлечь значения, выполните сортировку по этому столбцу.

 alter table linked_list add column position integer not null default 0;
 alter table linked_list add index position_index (position);
 select * from linked_list order by position;

Чтобы вставить значение по индексу 3, измените позиции строк 3 и выше, а затем вставьте:

 update linked_list set position = position + 1 where position >= 3;
 insert into linked_list (my_value, position) values ("new value", 3); 

Answer 2

Используйте решение Адриана, но вместо увеличения на 1 увеличьте его на 10 или даже 100.Тогда вставки можно будет рассчитать как половину разницы между тем, что вы вставляете, без необходимости обновлять все, что находится ниже вставки.Выберите число, достаточно большое, чтобы обработать среднее количество вставок. Если оно слишком мало, вам придется вернуться к обновлению всех строк с более высокой позицией во время вставки.

Answer 3

создайте таблицу с двумя столбцами, ссылающимися на себя, previousID и NextID.Если элемент является первым в списке, ПредыдущийID будет иметь значение NULL, если он последний, NextID будет иметь значение NULL.SQL будет выглядеть примерно так:

create table tblDummy
{
     PKColumn     int     not null, 
     PreviousID     int     null, 
     DataColumn1     varchar(50)     not null, 
     DataColumn2     varchar(50)     not null,  
     DataColumn3     varchar(50)     not null, 
     DataColumn4     varchar(50)     not null, 
     DataColumn5     varchar(50)     not null, 
     DataColumn6     varchar(50)     not null, 
     DataColumn7     varchar(50)     not null, 
     NextID     int     null
}

Answer 4

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

Вы можете узнать об этом больше здесь.

Надеюсь, это поможет.

Answer 5

Самый простой вариант — создать таблицу со строкой для каждого элемента списка, столбцом для позиции элемента и столбцами для других данных в элементе.Затем вы можете использовать ORDER BY в столбце позиции для получения данных в желаемом порядке.

create table linked_list
(   list_id   integer not null
,   position  integer not null 
,   data      varchar(100) not null
);
alter table linked_list add primary key ( list_id, position );

Чтобы манипулировать списком, просто обновите позицию, а затем вставьте/удалите записи по мере необходимости.Итак, чтобы вставить элемент в список 1 по индексу 3:

begin transaction;

update linked_list set position = position + 1 where position >= 3 and list_id = 1;

insert into linked_list (list_id, position, data)
values (1, 3, "some data");

commit;

Поскольку операции со списком могут требовать нескольких команд (например, для вставки потребуются INSERT и UPDATE), убедитесь, что вы всегда выполняете команды внутри транзакции.

Разновидностью этого простого варианта является увеличение позиции на некоторый коэффициент для каждого элемента, скажем, на 100, чтобы при выполнении INSERT вам не всегда приходилось перенумеровывать позиции следующих элементов.Однако это требует немного больше усилий, чтобы определить, когда увеличивать следующие элементы, поэтому вы потеряете простоту, но выиграете производительность, если у вас будет много вставок.

В зависимости от ваших требований могут понравиться и другие варианты, например:

• Если вы хотите выполнять много манипуляций со списком, а не много извлечений, вы можете предпочесть, чтобы столбец идентификатора указывал на следующий элемент в списке, а не использовал столбец позиции.Затем вам потребуется итеративная логика при извлечении списка, чтобы привести элементы в порядок.Это можно относительно легко реализовать в хранимой процедуре.

• Если у вас много списков, есть быстрый способ сериализации и десериализации вашего списка в текстовый/двоичный формат, и вы хотите сохранить и получить только весь список, то сохраните весь список как одно значение в одном столбце.Вероятно, это не то, о чем вы здесь спрашиваете.

Answer 6

Этот пост старый, но я все равно принесу свои 0,02 доллара.Обновление каждой записи в таблице или наборе записей кажется безумием для решения проблемы упорядочения.объем индексации тоже сумасшедший, но похоже, что большинство это приняло.

Сумасшедшее решение, которое я придумал для уменьшения количества обновлений и индексации, состоит в том, чтобы создать две таблицы (и в большинстве случаев вы все равно не сортируете все записи только в одной таблице).Таблица A для хранения записей сортируемого списка и таблица B для группировки и хранения записей порядка в виде строки.строка заказа представляет собой массив, который можно использовать для упорядочивания выбранных записей либо на веб-сервере, либо на уровне браузера приложения веб-страницы.

Create Table A{
Id int primary key identity(1,1),
Data varchar(10) not null
B_Id int
}

Create Table B{
Id int primary key Identity(1,1),
GroupName varchat(10) not null,
Order varchar(max) null
}

Формат строки заказа должен быть идентификатором, позицией и некоторым разделителем, по которому можно разделить() вашу строку.в случае пользовательского интерфейса jQuery функция .sortable('serialize') выводит для вас строку заказа, совместимую с POST, которая включает идентификатор и позицию каждой записи в списке.

Настоящая магия заключается в том, как вы можете изменить порядок выбранного списка, используя сохраненную строку заказа.это будет зависеть от приложения, которое вы создаете.вот еще раз пример из jQuery для изменения порядка списка элементов: http://ovisdevelopment.com/oramincite/?p=155

Answer 7

https://dba.stackexchange.com/questions/46238/linked-list-in-sql-and-trees предлагает трюк с использованием столбца позиции с плавающей запятой для быстрой вставки и упорядочивания.

Также упоминается специализированный SQL Server 2014. иерархияid особенность.

Answer 8

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

Самый простой метод — присвоить порядковый номер каждой записи в таблице (например,1, 2, 3, ...).Затем, когда вы получаете записи, укажите порядок в порядковом столбце, чтобы вернуть их в порядок.

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

Несколько более сложный, но и более гибкий подход — хранить информацию о членстве в списке или списках в отдельной таблице.В таблице потребуется 3 столбца:Идентификатор списка, порядковый номер и указатель внешнего ключа на запись данных.При таком подходе базовые данные ничего не знают о своем членстве в списках и могут легко быть включены в несколько списков.

Answer 9

Я думаю, что гораздо проще добавить созданный столбец Datetime тип и столбец позиции int, поэтому теперь у вас могут быть дублирующиеся позиции, в операторе выбора используйте order by позиция, созданная опция описания, и ваш список будет получен по порядку.

Answer 10

Это то, что я сам некоторое время пытался понять.Лучший способ, который я нашел на данный момент, — создать одну таблицу для связанного списка, используя следующий формат (это псевдокод):

LinkedList(

• ключ1,
• информация,
• ключ2

)

key1 — отправная точка.Key2 — это внешний ключ, ссылающийся на самого себя в следующем столбце.Итак, ваши столбцы будут ссылаться на что-то вроде этого

столбец 1

• ключ1 = 0,
• информация = 'привет'
• ключ2 = 1

Key1 — это первичный ключ столбца 1.key2 — это внешний ключ, ведущий к ключу 1 столбца 2.

столбец 2

• ключ1 = 1,
• информация = 'Как дела'
• ключ2 = ноль

key2 из col2 имеет значение null, поскольку он ни на что не указывает.

Когда вы впервые вводите столбец в таблицу, вам необходимо убедиться, что для параметра key2 установлено значение null, иначе вы получите сообщение об ошибке.После ввода второго столбца вы можете вернуться и установить для ключа key2 первого столбца первичный ключ второго столбца.

Это лучший способ ввести множество записей одновременно, а затем вернуться и соответствующим образом установить внешние ключи (или создать графический интерфейс, который сделает это за вас).

Вот реальный код, который я подготовил (весь реальный код работал на MSSQL.Возможно, вам захочется изучить версию SQL, которую вы используете!):

createtable.sql

create table linkedlist00 (

key1 int primary key not null identity(1,1),

info varchar(10),

key2 int

)

Register_foreign_key.sql

alter table dbo.linkedlist00

add foreign key (key2) references dbo.linkedlist00(key1)

*Я поместил их в два отдельных файла, потому что это нужно сделать в два этапа.MSSQL не позволит вам сделать это за один шаг, поскольку таблица еще не существует, на которую можно было бы ссылаться по внешнему ключу.

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

Пример:

Допустим, у вас есть бюрократия, которая сохраняет формы.

Допустим, у них есть таблица под названием картотека

ФайлКабинет(

• Идентификатор кабинета (ПК)
• Идентификатор файлов (FK))

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

Файлы(

• Идентификатор файла (ПК)

• Идентификатор файла (fk)

• Идентификатор следующего файла (fk)

)

это служит контейнером для файлов

Файл(

• Идентификатор файла (ПК)

• Информация о файле

)

это конкретный файл

Могут быть лучшие способы сделать это, и они есть, в зависимости от ваших конкретных потребностей.Пример просто иллюстрирует возможное использование.

Answer 11

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

Answer 12

Увеличьте индекс SERIAL на 100, но вручную добавьте промежуточные значения с индексом, равным Prev+Next / 2.Если вы когда-нибудь насытите 100 строк, измените порядок индекса обратно на 100.

Это должно поддерживать последовательность с первичным индексом.