[Jeremy Cols's InnoDB] 4.The physical structure of InnoDB index pages

이 글은 다음의 블로그를 제가 그냥 번역한 겁니다.

http://blog.jcole.us/2013/01/07/the-physical-structure-of-innodb-index-pages/?relatedposts_exclude=846

이상한 번역내용이 있을 수도 있습니다.

번역 내용은 100% 믿지 마세요~~~

The physical structure of InnoDB index pages

여기서는 INDEX page의 물리적인 구조에 대해 다룬다.

Everything is an index in InnoDB

물리적인 구조를 다루기 전에 InnoDB에 이해하고 있는것이 중요하다. InnoDB의 모든 것은 index라는 것을 이해하는 것이 중요하다. 이것은 무슨 말인가?

1. 모든 테이블은 Primary Key를 가지고 있다, 만약 CREATE TABLE시에 아무것도 명시 하지 않으면 첫번째의  non-null Unique Key를 사용하려고 하고, 만약 실패하면, 48bit의 숨겨진 Row ID를 사용하여 자동으로 PK를 생성하여 거기에 데이터를 저장하려고 한다. 즉, 무조건 PK가 있어야 한다는 말이고, 생성하지 않으면, PK를 자동으로 생성하기 때문에 각 row마다 불필요한 6 bit의 정보값을 추가적으로 저장하게 된다는 것이다.

2. Primary Key가 아닌 row data는 Primary Key의 index structure에 저장된다. 이것을 우리는 clustered key(index)라고 부른다. 이 인덱스 구조는 PK에 기반하여 만들어지고, row data는 Key에 추가되어 저장된다. (추가적으로 MVCC를 위한 필드도 포함된다)

3. Secondary key는 동일한 index 구조로 저장되는데, 자신의 key 정보를 가지고 있고, 거기에 Primary key 값인 PKV를 포함하여 가지고 있다.

InnoDB는 위에서 설명한 것고 같은 구조를 가지고 있으며, 이얷은 DBA 입장에서 table과 index를 동시에 생각해야 한다는 것을 의미한다.

Overview of INDEX Page Structure

모든 인덱스 페이지는 전반적으로 다음과 같은 구조를 가진다.

위 구조의 주요 부분들에 대한 설명은 다음과 같다. (순서대로 아님)

• FIL header와 trailer : 이 부분은 모든 페이지에 동일하게 들어있는 부분이다. 같은 레벨의 인덱스 페이지에 대한 previous page와 next page에 대한 포인터 정보가 들어가 있다. 인덱스 key들은 순서대로 정렬되어있다. 모든 페이지들은 같은 레벨에 대해서 double-linked list로 구성되어있다.
  
• FSEG header : index root page의 FSEG header는 이 인덱스에 의해 사용되는 file segment에 대한 포인터 정보를 가지고 있다. 모든 다른 index page의 FSEG headers는 사용하지 않고, zero 값으로 채워져 있다.
  
• INDEX header:INDEX 페이지에 연관된 많은 정보 와 record mangement정보가 포함된다.
  
• System records : InnoDB는 infimum과 supremum이라고 불리는 두가지의 system record를 가지고 있다. 이 record들은 그 페이지의 지정된 장소에 저장되고, 그렇기 때문에 페이지의 byte offset을 기반으로 직접적으로 찾을 수 있다.
  
• User records : 실질적인 데이터가 저장된다. 모든 record들은 variable-width header와 실질적인 컬럼 데이터를 가지고 있다. header는 next record를 가르키는 포인터 정보를 가지고 있는데, 페이지에 순서대로 다음 record의 offset 정보를 통해 가르킨다. 그리고 이 정보는 singly-linked list로 구헌되어있다.
  
• The page directory : page directory는 FIL trailer를 TOP으로 해서 아래로 점점 커지는 구조로 되어있다. 이 구조안에는 이 페이지의 몇몇 record에 대한 pointer정보(매 4번째 8번째 record)를 포함한다.
  

The INDEX header

각 index page에 있는 INDEX header는 fixed-width로 되어있고, 구조는 다음과 같다.

주요 부분에 대한 설명은 다음과 같다.(순서대로가 아니다)

• Index ID : 이 페이지가 속한 index의 ID 정보를 가지고 있다.
  
• Format Flag : 이 페이지의 record의 포맷 정보로 "Number of Heap Records" 필드의 high bit(0x8000)안에 그 값이 저장된다. 값은 둘중 하나이다. COMPACT 이거나 REDUNDANT
• Maximum Transaction ID : 이 페이지에 저장된 레코드 중 가장 최근에 수정된 transaction ID 값
• Number of Heap Records : 이 페이지안의 레코드의 총 수 infimum과 supremum system record를 포함하며, garbage(deleted) record도 포함한 값이다.
  
• Number of Records : 삭제되지 않은 이 페이지안의 사용자 record의 총 수
• Heap Top Position : 현재 사용되는 space의 end offset 의 byte 수. heap top과 페이지의 end 사이의 공간은 모두 free 영역이다.
  
• First Garbage Record Offset : garbage(deleted) record의 리스트의 첫번째 엔트리를 나타내는 포인터 정보. 이 리스트는 singly-linked list로 구성되어있으며, next record값만 가지고 있다. ( 이 리스트를 InnoDB에서는 free로 부르기 때문에 조금은 헛갈릴수 있다.)
• Garbage Space : garbage record list에 저장된 삭제된 레코드에 의해 낭비되고 있는 총 byte수 이다. 
• Last Insert Position : page안의 가장 최근에 insert된 레코드의 offset byte 수
• Page Direction : 이 값은 현재 page direction으로 사용되고 있다. : LEFT, RIGHT, NO_DIRECTION. 이 값은 이 페이지에 insert가 순차적으로 되었는지, random하게 되었는지를 알수있게 하는 지표가 된다. 각 insert마다, 가장 마지막에 insert된 레코드의 위치정보가 읽혀지고, 현재 insert되는 레코드의 key와 비교하여 입력할 공간의 위치가 결정된다.
  
• Number of Inserts in Page Direction : 한번 page direction이 set되면, 그 뒤에 따르는 insert들은 그 direction이 reset되지 않는다. 대신, direction 값은 점차적으로 증가하게 된다.
  
• Number of Directory Slots : slot이라고 부르는 영역안에 page directory의 사이즈가 저장된다. 이 slot은  각각 16-bit byte offset으로 되어있다.
  
• Page Level: index에서 이 페이지에 대한 level정보를 저장한다. Leaf Page는 level 0에서 시작하여 하나씩 증가하는데, 그것은 B+tree의 구조로서 만들어 진다. 일반적인 3-level의 B+tree구조에서 root는 level 2가 되고, 몇몇 internal non-leaf page들은 level 1이 되고, leaf page들은 level 0이 된다.
  

Record format: redundant versus compact

COMPACK row format은 Barracuda table format의 새로운 포맷이다. 이전에는 Antelope format의 REDUNDANT record(row) format을 사용하였다. COMPACK format은 data dictionary 에서 얻을 수 있는 각각의 레코드에 저장된 여분의 정보를 삭제한 포맷이다. 여기서 여분의 정보란, 각 컬럼의 사이즈라던지, null유무, 가변길이 여부와 같은 것이다.

An aside on record pointers

Record pointer는 몇몇 여러 영역에서 사용된다. : Index header의 가장 최근의 Insert position field, page directory의 모든 값들, 그리고, system record와 user record의 "next record" pointer가 바로 그것이다. 모든 레코드들은 header를 포함하고, 그게 따른 record data를 가지고 있다. Record pointer는 record data의 첫번째 바이트의 위치를 가르키고 있다. 그기로 그것은 header와 record data 사이를 의미한다. 이것은 그 포인터 위치를 기본으로 해서 역으로 읽으면 header정보를 읽는 것이고, 순대로 읽으면 record data를 읽는 다는 것을 의미한다.

system과 user record의 next record가 항상 첫번째 field의 앞을 가르킨다는 것은 variable-witdh record data의 분석 없이 데이터를 쉽게 읽을 수 있다는 것을 의미한다.

System records: infimum and supremum

모든 INDEX page는 두개의 system record를 가지고 있는데, infimum과 supremum이라고 하는 것이다. 이것은 각각 페이지의 고정된 위치인 offset 99위치와 offset 112위치에 위치한다.

이 두 system record는 그들 앞에 일반적인 record header를 가지고 있고, infimum과 supremum은 일반적인 literal string 데이터를 가지고 있다. header field에 대한 설명은 나중에 하기로 한다. 여기서 중요한 점은 첫번째 필드가 next record 포인터로 사용되고 있다는 것이다.

-참고-

지금 그림에 INDEX System Records라고 되어있기는 하지만, 설명을 잘 읽어 보면 저 그림은 INDEX System REcords에 대한 그림이 아니라, 각각 인덱스 페이지의 Header 정보 다음의 영역으로 판단된다.

The infimum record

infimum record는 그 페이지에서 가질 수 있는 key의 값 중 가장 낮은 값을 나타낸다. 그것의 next record pointer는 그 페이지의 가장 낮은 key 값을 가진 user record를 가르킨다. infimum은 순서대로 user record를 스캐닝할때 사용하기에 좋다.

The supremum record

supremum record는 그 페이지에서 가질 수 있는 key의 값중 가장 높은 값을 나타낸다. 그것의 next record pointer는 항상 zero를 가지는데, 이것은 NULL을 표현하며, 이것은 실질적으로 항상 invalid position을 나타낸다. 그 페이지의 가장 높은 값을 가진 user record의 next record pointer는 항상 supremum을 가르킨다.

User records

user record의 물리적인 디스크상의 포맷은 다음에 자세히 하기로 하고, 여기서는 그것이 상당히 복잡하고, 많은 설명이 필요하다는 것만 알고 넘어가자.

User record는 insert될때 page의 body 영역에 순서대로 추가된다. key 순으로 singly-linked로 각각 record header의 next record pointer가 연결된다. singly-linked list는 infimum부터 시작하여 키의 순서대로 연결되고, supremum에서 끝나게 된다. 이 리스트를 사용하는 것은 페이지에서 키 순서대로 모든 데이터를 스캔할때 사용한다.

INDEX header에서 next page pointer를 사용하는 것은 페이지에서 페이지로 키 순서대로 scan하고자 할때 사용한다. 이것은 키 순서대로 테이블 스캔을 다음과 같이 진행한다는 것이다. 

1. 인덱스의 첫번째 페이지 즉, 가장 낮은 키를 가진 페이지를 찾아서 시작한다. ( 이 페이지는 B+tree로 구성되어있다.)
2. infimum 정보를 읽어서 "next record" 포이터의 정보를 따라간다.
   
3. record가 supremum이 되면 5번으로 넘어간다. 그렇지 않으면, record contents를 읽고 실행한다.
   
4. next record pointer을 따라간다. 3번으로 넘어간다.
   
5. next page pointer가 NULL을 가르키면, 그만한다. 그렇지 않으면 next page pointer가 가르키는 다음 페이지로 넘어간다.
   

record가 singly-linked 로 되어있기 때문에 역순으로 인덱스를 읽는 것은 쉬운일이 아니다. 이와 관련된 것은 다음에 다시 이야기 한다.

The page directory

page directory 는 FIL trailer에서 시작하여 user record를 향해 거꾸로 사이즈가 증가한다. page directory는 페이지의 4번째, 8번째 record 를 가르키는 포인터를 포함한다. 추가적으로 infimun과 supremum 을 위한 entry도 포함한다.

이 page directory는 페이지 안의 간단한 16-bit offset pointer의 dynamically-sized arry 이다. 이것이 언제 쓰이는지는 다음에 다시 설명한다.

Free Space

user record와 page directory 사이의 space로서 사용하지 않는 공간을 의미한다.