Database System Concepts - Slotted Page Structure

Chan Young Jeong·2023년 3월 18일
0

Database System Concepts

목록 보기
2/14
post-thumbnail

데이터베이스 시스템에서 가변 길이 레코드를 저장하는 방법 중 하나는 슬롯 페이지 구조를 사용하는 것입니다.

Slotted Page Structure란?

슬롯 페이지 구조에서는 페이지를 고정 크기의 슬롯으로 나누고 각 슬롯에는 레코드의 길이와 슬롯 내 오프셋과 같은 레코드에 대한 정보를 저장하는 슬롯 헤더가 포함됩니다.

  • 레코드들 간에 빈 공간이 없도록 레코드들은 페이지 안에서 위치가 변경될 수 있습니다. 이 때 위치가 변경된 레코드를 가리키는 slot의 포인터는 변경된 위치를 가리킬 수 있도록 update되어야 합니다.

  • 외부 포인터는 레코드를 직접 가리켜서는 안됩니다. 대신에 헤더에 있는 레코드의 slot을 가리켜야 합니다.
    -> 외부 포인터라고 함은 예를 들어 인덱스를 의미합니다. 만약 어떤 레코드의 인덱스가 레코드를 직접 가리키고 있으면, 레코드의 위치가 옮겨 질 때마다 인덱스의 포인터도 update가 이루어져야 해서 디비 시스템적으로 봤을 때 비효율적입니다. 따라서 인덱스의 포인터는 레코드를 직접 가리키는 것이 아닌 헤더에 있는 레코드의 slot을 가리킬 수 있도록 합니다.

Block Header contains

  • number of record(slot) entries

  • end of free space in the block

    free space의 끝을 알고 있기 때문에 fress space의 크기를 계산할 수 있음. (위 그림에서 빨간색 화살표를 의미)
  • location and size of each record
    각 slot에는 record의 size와 record의 위치를 나타내는 location(점선 표시의 화살표)이 저장됩니다.

Slotted Page Structured에서 record 삽입

  • slot 공간과 삽입할 record의 크기만큼 free space가 있는지 확인합니다.
    (이 때 빈 slot을 활용할 수도 있습니다.)
  • 헤더의 # Entries가 갱신된다. 1 증가.
  • free space 뒷 부분에 레코드가 추가됩니다.(free space를 contiguous하게 유지하기 위해)

Slotted Page Structured에서 record 삭제

Delete Record3

  • 헤더의 # Entries가 갱신된다. 1 감소

  • 삭제된 slot에는 -1을 저장하여 더이상 사용하지 않는 slot이라고 표시한다.

  • free space는 contiguous 해야하기 때문에 record1과 record2를 옮겨 주면서 slot의 location과 End of free space를 갱신해준다.

record3의 slot도 삭제해야하나?

No! record3의 slot은 그대로 남겨둔다. 왜냐하면 외부 포인터는 slot을 가리키고 있기 때문이다. record3의 slot이 삭제되면 나머지 slot의 위치도 upate 되는데 그렇게 되면 외부 포인터가 가리키는 위치가 변경되어 잘못된 위치를 가리킬 수 있게 된다.

대신에 record3의 slot에 -1을 저장하여 더이상 사용하지 않는 slot이라고 표시한다.

Blocking factor를 구해보자

고정 길이 레코드 -> ⌊Block size / record size⌋

가변 길이 레코드 -> ⌊(Block size - header field) / (record size + slot size )⌋

  • header field : # of Entries , Free space pointer
  • record size : 가변 길이이지만 평균적인 record의 크기
  • slot size : slot의 크기는 고정 (size, location)

출처
Java T Point

0개의 댓글