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

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

<p>сохраните в таблице целочисленный столбец с именем 'position'. запишите 0 для первого элемента в вашем списке, 1 для второго элемента и т.д. индексируйте этот столбец в вашей базе данных, и, когда вы хотите извлечь свои значения, выполните сортировку по этому столбцу.</p><pre><code> 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; </code></pre><p>чтобы вставить значение в индекс 3, измените положения строк 3 и выше, а затем вставьте:</p><pre><code> update linked\_list set position = position + 1 where position >= 3; insert into linked\_list (my\_value, position) values ("new value", 3); </code></pre>

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

<p>создать таблицу с двумя самоссылающимися столбцами previousid и nextid. если элемент является первым в списке, previousid будет нулевым, если это последний, nextid будет нулевым. sql будет выглядеть примерно так:</p><pre><code>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 } </code></pre>

<p>связанный список может быть сохранен с использованием рекурсивных указателей в таблице. это почти те же иерархии, которые хранятся в sql, и это использует рекурсивный шаблон ассоциации.</p><p>вы можете узнать больше об этом <a href="http://www.tomjewett.com/dbdesign/dbdesign.php?page=recursive.php">здесь</a> .</p><p>надеюсь, это поможет.</p>

<p>простейшим вариантом будет создание таблицы со строкой на элемент списка, столбцом для позиции элемента и столбцами для других данных в элементе. затем вы можете использовать order by в столбце позиции, чтобы получить в нужном порядке.</p><pre><code>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 ); </code></pre><p>для управления списком просто обновите позицию, а затем вставьте/удалите записи по мере необходимости. итак, чтобы вставить элемент в список 1 по индексу 3:</p><pre><code>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; </code></pre><p>поскольку для операций в списке могут потребоваться несколько команд (например, для вставки потребуются insert и update), убедитесь, что вы всегда выполняете команды в транзакции.</p><p>разновидностью этого простого варианта является увеличение позиции на некоторый коэффициент для каждого элемента, скажем, 100, чтобы при выполнении insert вам не всегда приходилось изменять нумерацию позиций следующих элементов. однако это требует немного больше усилий, чтобы решить, когда увеличивать следующие элементы, поэтому вы теряете простоту, но получаете производительность, если у вас будет много вставок.</p><p>в зависимости от ваших требований могут подойти другие варианты, такие как:</p><ul> <li> <p>если вы хотите выполнить много манипуляций со списком, а не много поисков, вы можете предпочесть столбец идентификатора, указывающий на следующий элемент в списке, вместо использования столбца позиции. затем вам нужно выполнить итеративную логику в поиске списка, чтобы упорядочить элементы. это может быть относительно легко реализовано в хранимой процедуре.</p> </li> <li> <p>если у вас много списков, быстрый способ сериализации и десериализации вашего списка в текстовый/двоичный формат, и вы когда-либо захотите сохранить и извлечь весь список, то сохраните весь список как одно значение в одном столбце. вероятно, не то, что вы просите здесь, хотя.</p> </li> </ul>

<p> <a href="https://dba.stackexchange.com/questions/46238/linked-list-in-sql-and-trees">https://dba.stackexchange.com/questions/46238/linked-list-in-sql-and-trees</a> предлагает хитрость использования столбца с плавающей запятой для быстрой вставки и упорядочения.</p><p>в нем также упоминается специализированная функция sql server 2014 <a href="http://technet.microsoft.com/en-us/library/bb677173.aspx">ierarchyid</a> .</p>

<p>этот пост старый, но все равно собираюсь отдать мой .02 $. обновление каждой записи в таблице или наборе записей звучит безумно, чтобы решить порядок. количество индексации тоже сумасшедшее, но, похоже, большинство приняли это.</p><p>сумасшедшее решение, которое я придумал для сокращения обновлений и индексации, состоит в создании двух таблиц (и в большинстве случаев вы все равно не сортируете все записи только в одной таблице). таблица a для хранения записей сортируемого списка, а таблица b - для группировки и хранения записи порядка в виде строки. строка заказа представляет собой массив, который можно использовать для упорядочения выбранных записей либо на веб-сервере, либо на уровне браузера приложения веб-страницы.</p><pre><code>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 } </code></pre><p>формат строки заказа должен быть id, position и некоторый разделитель для разделения () вашей строки. в случае jquery ui функция .sortable ('serialize') выводит для вас строку заказа, которая является post дружественной, которая включает в себя идентификатор и позицию каждой записи в списке.</p><p>настоящая магия - это способ, которым вы решаете изменить порядок выбранного списка, используя сохраненную строку заказа. это будет зависеть от приложения, которое вы создаете. вот еще один пример из jquery для переупорядочения списка элементов: <a href="http://ovisdevelopment.com/oramincite/?p=155">http://ovisdevelopment.com/oramincite/?p=155</a> </p>

<p>есть несколько подходов, которые я могу придумать сразу, каждый с различным уровнем сложности и гибкости. я предполагаю, что ваша цель - сохранить порядок в поиске, а не требовать хранения в качестве фактического связанного списка.</p><p>простейшим способом будет присвоение порядкового значения каждой записи в таблице (например, 1, 2, 3, ...). затем при извлечении записей укажите порядок в столбце порядкового номера, чтобы вернуть их в порядок.</p><p>этот подход также позволяет извлекать записи без учета членства в списке, но допускает членство только в одном списке и может потребовать дополнительный столбец "идентификатор списка", чтобы указать, к какому списку принадлежит запись.</p><p>несколько более сложным, но и более гибким подходом было бы хранить информацию о членстве в списке или списках в отдельной таблице. таблице потребуется 3 столбца: идентификатор списка, порядковый номер и указатель внешнего ключа на запись данных. при таком подходе базовые данные ничего не знают о своем членстве в списках и могут быть легко включены в несколько списков.</p>

<p>это то, что я пытался выяснить некоторое время сам. наилучший способ, который я нашел до сих пор, - это создать одну таблицу для связанного списка в следующем формате (это псевдокод):</p><p>linkedlist (</p><ul> <li>key1,</li> <li>информация,</li> <li>key2</li> </ul><p>)</p><p>ключ1 является отправной точкой. key2 - это внешний ключ, который ссылается на себя в следующем столбце. таким образом, ваши столбцы будут ссылаться на что-то вроде этого</p><p><strong>col1</strong></p><ul> <li>ключ1 = 0,</li> <li>информация = 'привет'</li> <li>ключ2 = 1</li> </ul><p><em> key1 является первичным ключом col1. ключ2 - это внешний ключ, ведущий к ключу1 из col2 </em></p><p><strong>col2</strong></p><ul> <li>ключ1 = 1,</li> <li>информация = 'wassup'</li> <li>key2 = ноль</li> </ul><p><em> key2 из col2 имеет значение null, потому что ни на что не указывает </em></p><p>когда вы впервые вводите столбец для таблицы, вам нужно убедиться, что key2 имеет значение null, иначе вы получите ошибку. после ввода второго столбца вы можете вернуться назад и установить для key2 первого столбца первичный ключ второго столбца.</p><p>это лучший способ для одновременного ввода большого количества записей, затем вернитесь назад и соответственно установите внешние ключи (или создайте графический интерфейс, который сделает это за вас)</p><p>вот некоторый реальный код, который я подготовил (весь реальный код работал на mssql. возможно, вы захотите провести исследование для версии sql, которую вы используете!):</p><p><em> createtable.sql </em></p><pre><code>create table linkedlist00 ( key1 int primary key not null identity(1,1), info varchar(10), key2 int ) </code></pre><p><em> register\_foreign\_key.sql </em></p><pre><code>alter table dbo.linkedlist00 add foreign key (key2) references dbo.linkedlist00(key1) </code></pre><p>* я поместил их в два отдельных файла, потому что это нужно сделать в два этапа. mssql не позволит вам сделать это за один шаг, потому что таблица еще не существует для ссылки на внешний ключ.</p><p>связанный список особенно силен в <em> отношениях "один ко многим" </em>. итак, если вы когда-нибудь хотели сделать массив внешних ключей? ну, это один из способов сделать это! вы можете создать первичную таблицу, которая указывает на первый столбец в таблице связанных списков, а затем вместо поля "информация" вы можете использовать внешний ключ для нужной информационной таблицы.</p><p>пример:</p><p>допустим, у вас есть бюрократия, которая хранит формы.</p><p>допустим, у них есть таблица с именем <em> файловый шкаф </em></p><p>filecabinet (</p><ul> <li>кабинет id (пк)</li> <li>идентификатор файла (fk))</li> </ul><p><em> каждый столбец содержит первичный ключ для кабинета и внешний ключ для файлов. это могут быть налоговые формы, документы о медицинском страховании, квитанции о разрешении на поездку и т.д. </em></p><p>файлы (</p><ul> <li> <p>идентификатор файла (pk)</p> </li> <li> <p>идентификатор файла (fk)</p> </li> <li> <p>id следующего файла (fk)</p> </li> </ul><p>)</p><p><em> это служит контейнером для файлов </em></p><p>файл(</p><ul> <li> <p>идентификатор файла (pk)</p> </li> <li> <p>информация о файле</p> </li> </ul><p>)</p><p><em> это конкретный файл </em></p><p>могут быть лучшие способы сделать это, и есть, в зависимости от ваших конкретных потребностей. пример просто иллюстрирует возможное использование.</p>

<p>я думаю, что гораздо проще добавить созданный столбец типа <code>datetime</code> и столбец позиции <code>int</code>, так что теперь вы можете иметь дублирующиеся позиции, в операторе select используйте позицию <code>order by</code>, параметр desc selected и ваш список будет выбран по порядку.</p>

<p>увеличьте serial 'index' на 100, но вручную добавьте промежуточные значения с 'index', равным prev + next/2. если вы когда-нибудь насытите 100 строк, измените порядок индекса на 100 с.</p><p>это должно поддерживать последовательность с первичным индексом.</p>

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