SQL의 링크 된 목록

SQL의 링크 된 목록

---

연결 목록을 mysql 데이터베이스에 저장하는 가장 좋은 방법은 삽입이 간단하고 (즉, 매번 여러 항목을 다시 색인 할 필요가 없음) 목록을 순서대로 쉽게 꺼낼 수 있도록하는 것입니다.

---

테이블에 '위치'라는 정수 열을 저장하십시오. 목록의 첫 번째 항목에 대해 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); 

---

Adrian의 솔루션을 사용하지만 1 씩 증가하는 대신 10 또는 100까지 증가합니다. 그러면 삽입 아래의 모든 항목을 업데이트 할 필요없이 삽입하는 항목의 차이의 절반으로 삽입을 계산할 수 있습니다. 평균 삽입 횟수를 처리 할 수있을만큼 큰 숫자를 선택하십시오. 너무 작 으면 삽입하는 동안 더 높은 위치로 모든 행을 업데이트해야합니다.

---

두 개의 자체 참조 열 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
}

---

가장 간단한 옵션은 목록 항목 당 행, 항목 위치에 대한 열, 항목의 다른 데이터에 대한 열이있는 테이블을 만드는 것입니다. 그런 다음 위치 열에서 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 );

목록을 조작하려면 위치를 업데이트 한 다음 필요에 따라 레코드를 삽입 / 삭제하면됩니다. 따라서 인덱스 3의 목록 1에 항목을 삽입하려면

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를 수행 할 때 항상 다음 요소의 위치 번호를 다시 지정할 필요가 없습니다. 그러나 이렇게하려면 다음 요소를 늘릴시기를 결정하는 데 약간의 노력이 필요하므로 단순성을 잃지 만 삽입이 많으면 성능이 향상됩니다.

요구 사항에 따라 다음과 같은 다른 옵션이 매력적일 수 있습니다.

• 목록에서 많은 조작을 수행하고 많은 검색을 수행하지 않으려면 위치 열을 사용하는 대신 목록의 다음 항목을 가리키는 ID 열을 선호 할 수 있습니다. 그런 다음 항목을 순서대로 가져 오려면 목록 검색에서 논리를 반복해야합니다. 이것은 저장된 proc에서 비교적 쉽게 구현할 수 있습니다.

• 목록이 많고 목록을 텍스트 / 바이너리로 직렬화 및 역 직렬화하는 빠른 방법이고 전체 목록 만 저장하고 검색하려는 경우 전체 목록을 단일 열에 단일 값으로 저장합니다. 아마도 당신이 여기서 요구하는 것이 아닐 것입니다.

---

연결 목록은 테이블의 재귀 포인터를 사용하여 저장할 수 있습니다. 이것은 Sql에 저장되는 것과 매우 유사한 계층이며 재귀 적 연관 패턴을 사용합니다.

여기 (Wayback Machine 링크) 에서 자세히 알아볼 수 있습니다 .

이게 도움이 되길 바란다.

---

이 게시물은 오래되었지만 여전히 .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') 함수는 목록에있는 각 레코드의 ID와 위치를 포함하는 POST 친화적 인 주문 문자열을 출력합니다.

진짜 마술은 저장된 순서 지정 문자열을 사용하여 선택한 목록을 다시 정렬하는 방법입니다. 이는 구축중인 애플리케이션에 따라 다릅니다. 다음은 항목 목록을 다시 정렬하는 jQuery의 예제입니다. http://ovisdevelopment.com/oramincite/?p=155

---

https://dba.stackexchange.com/questions/46238/linked-list-in-sql-and-trees 는 빠른 삽입 및 순서 지정을 위해 부동 소수점 위치 열을 사용하는 트릭을 제안합니다.

또한 특수한 SQL Server 2014 hierarchyid 기능에 대해서도 언급 합니다.

---

이것은 내가 한동안 알아 내려고 노력해온 것입니다. 지금까지 찾은 가장 좋은 방법은 다음 형식을 사용하여 연결된 목록에 대한 단일 테이블을 만드는 것입니다 (이것은 의사 코드입니다).

LinkedList (

• key1,
• 정보,
• key2

)

key1 is the starting point. Key2 is a foreign key linking to itself in the next column. So your columns will link something link something like this

col1

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

Key1 is primary key of col1. key2 is a foreign key leading to the key1 of col2

col2

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

key2 from col2 is set to null because it doesn't point to anything

When you first enter a column in for the table, you'll need to make sure key2 is set to null or you'll get an error. After you enter the second column, you can go back and set key2 of the first column to the primary key of the second column.

This makes the best method to enter many entries at a time, then go back and set the foreign keys accordingly (or build a GUI that just does that for you)

Here's some actual code I've prepared (all actual code worked on MSSQL. You may want to do some research for the version of SQL you are using!):

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)

*I put them into two seperate files, because it has to be done in two steps. MSSQL won't let you do it in one step, because the table doesn't exist yet for the foreign key to reference.

Linked List is especially powerful in one-to-many relationships. So if you've ever wanted to make an array of foreign keys? Well this is one way to do it! You can make a primary table that points to the first column in the linked-list table, and then instead of the "information" field, you can use a foreign key to the desired information table.

Example:

Let's say you have a Bureaucracy that keeps forms.

Let's say they have a table called file cabinet

FileCabinet(

• Cabinet ID (pk)
• Files ID (fk) )

each column contains a primary key for the cabinet and a foreign key for the files. These files could be tax forms, health insurance papers, field trip permissions slips etc

Files(

• Files ID (pk)

• File ID (fk)

• Next File ID (fk)

)

this serves as a container for the Files

File(

• File ID (pk)

• Information on the file

)

this is the specific file

There may be better ways to do this and there are, depending on your specific needs. The example just illustrates possible usage.

---

There are a few approaches I can think of right off, each with differing levels of complexity and flexibility. I'm assuming your goal is to preserve an order in retrieval, rather than requiring storage as an actual linked list.

The simplest method would be to assign an ordinal value to each record in the table (e.g. 1, 2, 3, ...). Then, when you retrieve the records, specify an order-by on the ordinal column to get them back in order.

This approach also allows you to retrieve the records without regard to membership in a list, but allows for membership in only one list, and may require an additional "list id" column to indicate to which list the record belongs.

An slightly more elaborate, but also more flexible approach would be to store information about membership in a list or lists in a separate table. The table would need 3 columns: The list id, the ordinal value, and a foreign key pointer to the data record. Under this approach, the underlying data knows nothing about its membership in lists, and can easily be included in multiple lists.

---

I think its much simpler adding a created column of Datetime type and a position column of int, so now you can have duplicate positions, at the select statement use the order by position, created desc option and your list will be fetched in order.

---

Increment the SERIAL 'index' by 100, but manually add intermediate values with an 'index' equal to Prev+Next / 2. If you ever saturate the 100 rows, reorder the index back to 100s.

This should maintain sequence with primary index.

---

A list can be stored by having a column contain the offset (list index position) -- an insert in the middle is then incrementing all above the new parent and then doing an insert.

참고URL : https://stackoverflow.com/questions/65205/linked-list-in-sql