it-swarm-es.tech

Lista enlazada en SQL

¿Cuál es la mejor manera de almacenar una lista vinculada en una base de datos mysql para que las inserciones sean sencillas (es decir, no tiene que reindexar un montón de cosas cada vez) y de tal manera que la lista se pueda sacar fácilmente en orden?.

55
magicrobotmonkey

Almacene una columna de enteros en su tabla llamada 'posición'. Registre un 0 para el primer elemento de su lista, un 1 para el segundo elemento, etc. Indexe esa columna en su base de datos, y cuando desee extraer sus valores, ordénelos por esa columna.

 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;

Para insertar un valor en el índice 3, modifique las posiciones de las filas 3 y superiores, y luego inserte:

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

Usando la solución de Adrian, pero en lugar de incrementar en 1, incremente en 10 o incluso en 100. Luego, las inserciones se pueden calcular a la mitad de la diferencia entre lo que se está insertando sin tener que actualizar todo lo que está debajo de la inserción. Elija un número lo suficientemente grande para manejar su número promedio de inserciones; si es demasiado pequeño, tendrá que recurrir a la actualización de todas las filas con una posición más alta durante una inserción.

16
cfeduke

cree una tabla con dos columnas de referencia automática PreviousID y NextID. Si el elemento es lo primero en la lista, PreviousID será nulo, si es el último, NextID será nulo. El SQL se verá algo así:

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
}
15
B0fh

Una lista enlazada se puede almacenar utilizando punteros recursivos en la tabla. Esto es muy parecido a las mismas jerarquías que se almacenan en Sql y esto está usando el patrón de asociación recursivo.

Puedes aprender más sobre esto aquí .

Espero que esto ayude.

4
user9252

La opción más sencilla sería crear una tabla con una fila por elemento de lista, una columna para la posición del elemento y columnas para otros datos en el elemento. Luego puede usar ORDER BY en la columna de posición para recuperar en el orden deseado.

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 );

Para manipular la lista, solo actualice la posición y luego inserte/borre los registros según sea necesario. Entonces, para insertar un artículo en la lista 1 en el índice 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;

Dado que las operaciones en la lista pueden requerir múltiples comandos (por ejemplo, una inserción requerirá un INSERTAR y una ACTUALIZACIÓN), asegúrese de que siempre realice los comandos dentro de una transacción.

Una variación de esta simple opción es tener un incremento de posición por algún factor para cada elemento, por ejemplo, 100, de modo que al realizar un INSERTO no siempre es necesario volver a numerar la posición de los siguientes elementos. Sin embargo, esto requiere un poco más de esfuerzo para calcular cuándo incrementar los siguientes elementos, por lo que perderá simplicidad pero obtendrá un mayor rendimiento si tendrá muchas inserciones.

Dependiendo de sus requisitos, otras opciones pueden apelar, como:

  • Si desea realizar muchas manipulaciones en la lista y no muchas recuperaciones, puede preferir tener una columna de ID que apunte al siguiente elemento de la lista, en lugar de utilizar una columna de posición. Luego, necesita la lógica iterativa en la recuperación de la lista para poder ordenar los elementos. Esto se puede implementar de forma relativamente fácil en un proceso almacenado.

  • Si tiene muchas listas, una forma rápida de serializar y deserializar su lista a texto/binario, y solo desea almacenar y recuperar la lista completa, luego almacene la lista completa como un solo valor en una sola columna. Probablemente no es lo que estás pidiendo aquí sin embargo.

4
Rory

https://dba.stackexchange.com/questions/46238/linked-list-in-sql-and-trees sugiere un truco de usar la columna de posición de punto flotante para inserciones y pedidos rápidos.

También menciona la función especializada SQL Server 2014 hierarchyid .

2
Vadzim

Este post es antiguo pero aun así voy a dar mi .02 $. Actualizar cada registro en una tabla o conjunto de registros parece una locura para resolver el orden. La cantidad de indexación también es una locura, pero parece que la mayoría lo ha aceptado.

La solución loca que se me ocurrió para reducir las actualizaciones y la indexación es crear dos tablas (y en la mayoría de los casos de uso no ordena todos los registros en una sola tabla de todos modos). La tabla A contiene los registros de la lista que se está ordenando y la tabla B para agrupar y mantener un registro de la orden como una cadena. la cadena de orden representa una matriz que se puede usar para ordenar los registros seleccionados en el servidor web o en la capa del navegador de una aplicación de página web.

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
}

El formato de la secuencia de la orden debe ser id, posición y algún separador para dividir () su cadena por. en el caso de la interfaz de usuario de jQuery, la función .sortable ('serializar') genera una cadena de orden para usted POST amigable que incluye el id y la posición de cada registro en la lista.

La verdadera magia es la forma en que elige reordenar la lista seleccionada utilizando la cadena de pedido guardada. Esto dependerá de la aplicación que estés creando. Aquí hay un ejemplo de jQuery para reordenar la lista de elementos: http://ovisdevelopment.com/oramincite/?p=155

2
FlyTigert

Hay algunos enfoques que se me ocurren de inmediato, cada uno con diferentes niveles de complejidad y flexibilidad. Supongo que su objetivo es preservar un pedido en recuperación, en lugar de requerir almacenamiento como una lista enlazada real.

El método más simple sería asignar un valor ordinal a cada registro en la tabla (por ejemplo, 1, 2, 3, ...). Luego, cuando recupere los registros, especifique un orden en la columna ordinal para volver a ponerlos en orden.

Este enfoque también le permite recuperar los registros sin importar la membresía en una lista, pero permite la membresía en una sola lista, y puede requerir una columna adicional "id de lista" para indicar a qué lista pertenece el registro.

Un enfoque un poco más elaborado, pero también más flexible sería almacenar información sobre la membresía en una lista o listas en una tabla separada. La tabla necesitaría 3 columnas: la identificación de la lista, el valor ordinal y un puntero de clave externa al registro de datos. Bajo este enfoque, los datos subyacentes no saben nada acerca de su pertenencia a listas y pueden incluirse fácilmente en múltiples listas.

1
Mike Monette

Esto es algo que he estado tratando de resolver por un tiempo yo mismo. La mejor manera que he encontrado hasta ahora es crear una sola tabla para la lista enlazada usando el siguiente formato (esto es pseudo código):

Lista enlazada(

  • llave1,
  • información,
  • llave2

)

key1 es el punto de partida. Key2 es una clave externa que se vincula a sí misma en la siguiente columna. Así que tus columnas enlazarán algo como esto.

col1

  • key1 = 0,
  • información = 'hola'
  • key2 = 1

Key1 es la clave principal de col1. key2 es una clave externa que conduce a la clave1 de col2

col2

  • key1 = 1,
  • información = 'wassup'
  • key2 = nulo

key2 from col2 se establece en nulo porque no apunta a nada

La primera vez que ingrese una columna para la tabla, deberá asegurarse de que la clave2 esté configurada en nula o se obtendrá un error. Después de ingresar la segunda columna, puede regresar y establecer la clave2 de la primera columna a la clave principal de la segunda columna.

Esto hace que el mejor método para ingresar muchas entradas a la vez, luego retroceda y establezca las claves externas en consecuencia (o cree una GUI que lo haga por usted)

Aquí hay algo de código real que preparé (todo el código real funcionó en MSSQL. ¡Es posible que desee hacer una investigación para la versión de SQL que está usando!):

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)

* Los puse en dos archivos separados, porque tiene que hacerse en dos pasos. MSSQL no le permitirá hacerlo en un solo paso, porque la tabla aún no existe para que la clave foránea haga referencia.

La Lista vinculada es especialmente poderosa en las relaciones de uno a muchos . ¿Así que si alguna vez has querido hacer una serie de claves externas? Bueno esta es una forma de hacerlo! Puede hacer una tabla principal que apunte a la primera columna en la tabla de lista enlazada, y luego, en lugar del campo de "información", puede usar una clave externa para la tabla de información deseada.

Ejemplo:

Digamos que tienes una burocracia que mantiene las formas.

Digamos que tienen una tabla llamada archivador

Archivador(

  • ID del gabinete (pk)
  • ID de archivos (fk)

cada columna contiene una clave principal para el gabinete y una clave externa para los archivos. Estos archivos pueden ser formularios de impuestos, documentos de seguro de salud, formularios de permisos de viaje, etc.

Archivos (

  • ID de archivos (pk)

  • ID de archivo (fk)

  • ID de archivo siguiente (fk)

)

esto sirve como un contenedor para los archivos

Expediente(

  • ID de archivo (pk)

  • Información sobre el archivo.

)

este es el archivo específico

Puede haber mejores maneras de hacer esto y las hay, dependiendo de sus necesidades específicas. El ejemplo simplemente ilustra el uso posible.

1
HumbleWebDev

Creo que es mucho más sencillo agregar una columna creada de Datetime tipo y una columna de posición de int, así que ahora puede tener posiciones duplicadas, en la declaración de selección use la posición order by, creó la opción desc y su lista se recuperará en orden.

1
Poncho

Incremente el 'índice' de SERIE en 100, pero agregue manualmente valores intermedios con un 'índice' igual a Anterior + Siguiente/2. Si alguna vez satura las 100 filas, reordene el índice a 100 segundos.

Esto debería mantener la secuencia con el índice primario.

0
Stephen

Se puede almacenar una lista haciendo que una columna contenga el desplazamiento (posición del índice de la lista): una inserción en el centro incrementa todo por encima del nuevo padre y luego hace una inserción.

0
Daniel Papasian