6조 물리적 데이터베이스 미션

1. B+ 트리 인덱싱

1-1. B-tree 의 등장 배경

• balanced tree가 왜 나왔는지
• 디스크 접근시 블록 단위로 접근하는 것을 사용해서. 디스크 접근 횟수를 최소화할 수 있음.
• 각 노드가 가질 수 있는 자식 포인터와 키의 개수를 최대한으로 늘려서 노드의 크기가 디스크 블록 크기에 맞춰지도록 설계. 하나의 디스크 블록이 4KB 크키라면B-Tree의 노드는 그 블록 크기에 맞춰 키와 포인터를 최대로 채우게 됨.
• "디스크 블록 크기에 맞춰서 설계된다”

1-2. B-tree 의 동작 방식

• 키(Key): 노드에 저장된 값들로, 각 키는 오름차순으로 정렬되어 저장됩니다.
• 자식 포인터(Child Pointer): 키와 키 사이의 범위에 해당하는 자식 노드를 가리킵니다.
• 검색
  • 루트 노드에서 시작: 검색은 루트 노드에서 시작합니다.
  • 키 비교: 현재 노드에서 각 키를 탐색하는 값과 비교합니다.
    • 탐색하려는 값이 현재 노드의 키 중 하나와 일치하면, 해당 키가 가리키는 데이터를 반환합니다.
    • 탐색하려는 값이 현재 노드의 키들과 일치하지 않으면, 탐색하려는 값이 어느 두 키 사이에 위치하는지를 확인한 후, 해당 범위의 자식 포인터를 따라 다음 노드로 이동합니다.
  • 리프 노드에 도달할 때까지 반복: 이 과정을 리프 노드에 도달할 때까지 반복합니다. 리프 노드에서도 값을 찾을 수 없다면, 해당 값은 트리에 존재하지 않습니다.
• 삽입
  1. 적절한 리프 노드 찾기: 삽입하려는 값을 기준으로 트리를 탐색하여 적절한 리프 노드를 찾습니다.
  2. 리프 노드에 삽입: 해당 리프 노드에 삽입하려는 값을 추가합니다.
     • 만약 노드에 빈 공간이 있다면, 단순히 키를 삽입하고 트리를 재정렬합니다.
  3. 노드 분할: 만약 노드가 가득 차게 되면(즉, 노드의 키 개수가 m-1개를 초과하게 되면), 노드를 분할해야 합니다.
     • 중간 키를 선택해 노드를 두 개로 분할하고, 중간 키를 부모 노드로 올려보냅니다.
     • 부모 노드가 가득 찼다면, 부모 노드 역시 분할하고, 이 과정이 루트 노드까지 반복될 수 있습니다. 이 경우 트리의 높이가 1 증가하게 됩니다.

1-3. B-tree와 B+ tree의 차이점

• b-tree는 여러개의 노드를 가질 수 있음. 하나의 블록에 여러 데이터들을 동시에 저장하기 위해서
• b-tre는 정렬되어있고 높이가 Log이기 때문에 빠르게 찾을 수 있다.
• b- tree는 균형 트리 구조를 유지하기 위해서 추가적인 연산이 수행된다. b-tree에서 몇 가지 규칙이 추가된 등장하게 되었음. 탐색을 위해서 노드를 찾아서 이동해야한다. 같은 레벨의 모든 키 값들이 정렬되어 있고 같은 레벨의 sbiling node는 연결리스트 형태로 이어져있음.
• 키 값은 중복될 수 있고 데이터 검색을 위해서는 반드시 leaf node까지 내려가야함. 검색 속도가 빠름?
• b-tree는 데이터베이스에서 쓰고 b+ 트리는 멀티 레벨인덱싱에서 쓴다.
• 이로 인해 B+Tree에서는 리프 노드들만 순차적으로 접근해도 모든 데이터를 쉽게 조회할 수 있습니다. 이는 특히 범위 검색(range query)에서 B+Tree가 더 유리하게 작용합니다.
• 하나의 B-Tree 노드(키와 자식 포인터를 포함한 데이터 구조 전체)가 디스크에서 한 번에 읽어올 수 있는 4KB 블록 크기와 일치하도록 설계
• 인덱스가 디스크에 저장되기 때문에, 인덱스를 사용한 검색 과정에서도 디스크 I/O가 발생합니다. 하지만 인덱스의 크기는 일반적으로 테이블의 데이터보다 훨씬 작기 때문에, 인덱스를 사용하는 것이 디스크 I/O를 최소화하고 성능을 크게 향상시킬 수 있습니다.
• 인덱스를 디스크에서 읽어올때의 효율성을 위해서 인덱스의 각 노드를 페이지 블록 크기와 맞추는 거야?
• 디스크 블록 크기는 운영체제와 파일 시스템에 의해 결정되며, 일반적으로 4KB, 8KB, 16KB 등으로 설정됩니다.
• 디스크 블록 크기는 B-Tree의 차수에 영향을 미칠 수 있습니다.

1-4.클러스터드 인덱스와 넌 클러스터드 인덱스

논클러스터드 인덱스의 키는 특정 열의 값을 기준으로 인덱스를 생성하지만, 인덱스는 실제 데이터의 위치를 직접 포함하지 않고, 데이터가 저장된 위치(즉, "포인터" 또는 "RID - Row Identifier")를 저장합니다.

정을 "북마크 조회" 또는 **"키 룩업"**이라고도 합니다.

1. 데이터는 별도의 위치(기본 테이블 또는 클러스터드 인덱스가 적용된 테이블)에서 관리되며, 논클러스터드 인덱스는 그 위치를 참조하는 역할을 합니다.
2. 데이터베이스 테이블의 특정 행(레코드)이 디스크의 어느 위치에 저장되어 있는지를 나타내는 고유한 식별자입니
3. 논클러스터드 인덱스에서 키가 가리키는 **RID(Row Identifier)**는 클러스터드 인덱스를 가리키거나, 클러스터드 인덱스가 없는 경우 디스크에서의 실제 데이터 위치를 가리킵니다. 이

1-5. 물리적으로 테이블을 저장하는 다양한 방법

• 힙 테이블 : 인덱스 없이 데이터만 쌓음. oracle default
• 클러스터드 인덱스
• nonclusted index

2. MySQL로 지도 정보를 저장하는 방법

지도 정보를 MySQL에 저장하기 위해서는 공간 데이터와 관련된 도구와 방법을 사용해야 합니다. MySQL은 지리적 좌표를 처리하고 저장할 수 있는 GIS(Geographic Information System) 기능을 제공합니다.

2-1. 공간 데이터 유형 사용

MySQL은 다음과 같은 공간 데이터 유형을 제공합니다:

• POINT: 좌표를 나타내는 단일 점을 저장합니다. 예를 들어, 특정 위치의 위도와 경도를 저장할 때 사용됩니다.
• LINESTRING: 여러 점을 연결한 선을 저장합니다. 예를 들어, 도로 경로를 저장할 때 사용됩니다.
• POLYGON: 닫힌 다각형을 저장합니다. 예를 들어, 특정 구역이나 지역을 정의할 때 사용됩니다.
• MULTIPOINT, MULTILINESTRING, MULTIPOLYGON: 각각 다중 점, 다중 선, 다중 다각형을 저장할 수 있습니다.

2-2. 지도 정보 저장 예시

아래는 MySQL에서 POINT 유형을 사용해 좌표를 저장하고, 공간 인덱스를 사용하는 방법에 대한 예시입니다.

sql코드 복사
CREATE TABLE locations (
    id INT AUTO_INCREMENT PRIMARY KEY,
    name VARCHAR(100),
    coordinates POINT,
    SPATIAL INDEX(coordinates)
);

• 데이터 삽입:

sql코드 복사
INSERT INTO locations (name, coordinates) VALUES
('Central Park', ST_GeomFromText('POINT(40.785091 -73.968285)')),
('Times Square', ST_GeomFromText('POINT(40.758896 -73.985130)'));

3. 공간 데이터 쿼리

공간 데이터는 특정 기능을 사용하여 검색할 수 있습니다. 예를 들어, 특정 반경 내의 모든 지점을 찾는 쿼리는 다음과 같이 작성할 수 있습니다:

sql코드 복사
SELECT name
FROM locations
WHERE ST_Distance_Sphere(coordinates, ST_GeomFromText('POINT(40.758896 -73.985130)')) < 1000;

위 쿼리는 Times Square에서 반경 1,000 미터 이내에 있는 모든 위치를 검색합니다.

요약

• MySQL은 다양한 인덱스 유형을 제공하며, 각각의 인덱스는 특정한 용도에 맞게 사용됩니다.
• 지도 정보나 지리적 데이터를 MySQL에 저장하려면, 공간 데이터 유형과 함께 공간 인덱스를 사용하여 효율적으로 데이터를 저장하고 검색할 수 있습니다. 이를 통해 GIS 응용 프로그램에서 지도 정보를 관리하는 데 MySQL을 효과적으로 사용할 수 있습니다.

3. MySQL에서 지원하는 인덱스의 종류와 용도

MySQL은 다양한 인덱스 유형을 지원하며, 각 인덱스는 특정한 용도에 따라 사용됩니다. 아래는 MySQL에서 지원하는 주요 인덱스의 종류와 그 용도입니다.

1. PRIMARY KEY (기본 키 인덱스)
   • 설명: PRIMARY KEY는 테이블에서 각 행을 고유하게 식별하는 열에 대해 정의됩니다. PRIMARY KEY는 자동으로 클러스터드 인덱스를 생성합니다.
   • 용도: 각 행을 고유하게 식별해야 할 때 사용되며, 테이블 내에서 하나만 존재할 수 있습니다.
2. UNIQUE INDEX (유니크 인덱스)
   • 설명: UNIQUE INDEX는 특정 열의 값이 고유하도록 보장합니다. 중복된 값을 허용하지 않습니다.
   • 용도: 고유한 값을 보장해야 하는 열에 사용됩니다. 예를 들어, 이메일 주소나 사용자 ID 등에서 사용됩니다.
3. INDEX (비클러스터드 인덱스)
   • 설명: 일반적인 인덱스로, 테이블의 데이터를 정렬하거나 특정 검색 작업을 빠르게 수행하기 위해 사용됩니다. 데이터의 물리적 순서에 영향을 주지 않습니다.
   • 용도: 자주 조회되는 열에 대해 인덱스를 설정하여 검색 성능을 향상시킵니다.
4. FULLTEXT INDEX (전문 검색 인덱스)
   • 설명: 텍스트 기반의 데이터에서 전체 텍스트 검색을 수행할 수 있는 인덱스입니다. 주로 VARCHAR, TEXT 등의 열에 적용됩니다.
   • 용도: 문서, 게시글 등에서 특정 단어 또는 문구를 검색할 때 사용됩니다. 예를 들어, 블로그 게시글 검색에 유용합니다.
5. SPATIAL INDEX (공간 인덱스)
   • 설명: 공간 데이터를 효율적으로 검색하기 위한 인덱스입니다. MySQL의 공간 데이터 유형(예: POINT, LINESTRING, POLYGON)에 사용됩니다.
   • 용도: 지도 정보나 지리적 데이터를 저장하고 검색할 때 사용됩니다. GIS(Geographic Information System)와 같은 응용 프로그램에서 유용합니다.
6. COMPOSITE INDEX (복합 인덱스)
   • 설명: 여러 열을 결합하여 하나의 인덱스를 생성합니다. 검색 조건에 여러 열이 포함될 때 유용합니다.
   • 용도: 다중 열을 사용한 쿼리의 성능을 최적화할 때 사용됩니다. 예를 들어, WHERE 절에 여러 열이 포함된 경우, 복합 인덱스가 성능을 크게 향상시킬 수 있습니다.