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

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

Ответ 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);

Ответ 2

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

Ответ 3

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

Ответ 4

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

Вы можете узнать больше об этом здесь (ссылка на Wayback Machine).

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

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

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

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

Ответ 6

Этот пост старый, но все еще собирается дать мой .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-friendly, которая включает идентификатор и позицию каждой записи в списке.

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

Ответ 7

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

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

Ответ 8

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

LinkedList (

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

)

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

col1

key1 = 0,
information = 'hello'
key2 = 1

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

col2

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

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

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

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

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

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

Пример:

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

Скажем, у них есть таблица с именем file cabinet

FileCABINET (

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

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

Файлы (

Идентификатор файлов (pk)
Идентификатор файла (fk)
Следующий идентификатор файла (fk)

)

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

Файл (

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

)

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

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

Ответ 9

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

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

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

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

Ответ 10

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

Ответ 11

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

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

Ответ 12

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