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

Question

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

Answer 1

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

Answer 2

Сохраните в таблице целочисленный столбец с именем 'position'. Запишите 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 3

создать таблицу с двумя самоссылающимися столбцами PreviousID и NextID. Если элемент является первым в списке, PreviousID будет нулевым, если это последний, NextID будет нулевым. 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

Самым простым вариантом будет создание таблицы со строкой на элемент списка, столбцом для позиции элемента и столбцами для других данных в элементе. Затем вы можете использовать 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;

Поскольку для операций в списке могут потребоваться несколько команд (например, для вставки потребуются ВСТАВКА и ОБНОВЛЕНИЕ), убедитесь, что вы всегда выполняете команды в транзакции.

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

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

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

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

Answer 5

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

Подробнее об этом можно узнать здесь .

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

Answer 6

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

В нем также упоминается специализированная функция SQL Server 2014 ierarchyid .

Answer 7

Этот пост старый, но все равно собираюсь отдать мой .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
}

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

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

Answer 8

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

LinkedList (

• key1,
• информация,
• key2

)

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

col1

• key1 = 0,
• информация = 'привет'
• key2 = 1

Ключ1 является первичным ключом col1. ключ2 - это внешний ключ, ведущий к ключу1 из col2

col2

• key1 = 1,
• information = 'wassup'
• key2 = null

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 не позволит вам сделать это за один шаг, потому что таблица еще не существует для ссылки на внешний ключ.

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

Пример:

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

Допустим, у них есть таблица с именем картотечный шкаф

FileCABINET (

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

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

Files (

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

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

• ID следующего файла (fk)

)

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

Файл (

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

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

)

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

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

Answer 9

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

Answer 10

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

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

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

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