SQLite 의 B-Tree 디 테 일 분석 실현

SQLite 가 외부 에 저 장 된 데이터 베 이 스 는 B-Tree 로 구성 되 어 있 습 니 다.B-tree 에 대한 세부 사항 은****Donald E.Knuth,THE ART OF COMPUTER PROGRAMMING,Volume 3:**"Sorting And Searching",pages 473-480 을 참고 하 십시오.Addison-Wesley**Publishing Company,Reading,Massachusetts.*기본 사상 은 파일 에 포 함 된 모든 페이지 에 N 개의 데이터베이스 입구 와 N+1 개의 하위 페이지 를 가리 키 는 지침 을 포함 합 니 다.파일 을 여러 페이지 로 나 누 어 저장 하 다.메모리 페이지 관리 체제 때문에 왜 그 랬 어 요?외 장 에 있 는 모든 페이지 는 B 나무의 한 노드 이다.Ptr(0)|Key(0)|Ptr(1)|Key(1)|.모든 Ptr(1)가 가리 키 는 페이지 와 하위 페이지 의 모든 key 의 값 은 Key(0)보다 크 고 Key(1)보다 작 습 니 다.모든 Ptr(N)가 가리 키 는 페이지 와 하위 페이지 의 key 값 은 Key(N-1)보다 큽 니 다.특정한 키 를 알 기 위해 서 는 디스크 에서 O(long(M)로 읽 어야 합 니 다.그 중에서 M 은 나무의 단계 입 니 다.메모리 에서 찾 을 수 없 으 면 페이지 가 끊 깁 니 다.주로 메모리 에서 찾 을 수 없 는 문 제 를 해결 하 는 것 이다.한편 으로 는 좀 바 꿔 주세요.한편 으로 는 좀 바 꿔 주세요.바 꿀 때 하 드 디스크 의 어느 페이지 에 있 는 지 찾 아야 합 니 다.B 트 리 의 장점 은 블록 저장 장치 에 적합 하 다 는 것 이다.)이용 하기 때문에 그들 이 어느 페이지 에 있 는 지 알 수 있다.SQLite 구현 에 있어 서 하나의 파일 은 1 개 또는 너무 독립 된 BTree 를 포함 할 수 있 습 니 다.모든 BTree 는 루트 페이지 의 색인 으로 표 시 됩 니 다.모든 입구 의 키 와 데이터 가 유효 부하(payload)를 구성한다.데이터베이스 의 한 페이지 에는 고정된 유효 부하 총량 이 있다.미리 설 정 된 값 보다 부하 가 많 으 면 나머지 바이트 가 넘 치 는 페이지 에 저 장 됩 니 다.입구 의 유효 부하 에 전방 향 포인터(the preceding pointer)가 한 칸(cell)을 구성한다.모든 페이지 에 작은 머리 가 있 고 Ptr(N)포인터 와 다른 정 보 를 포함 합 니 다.예 를 들 어 key 와 데이터 의 크기 등 입 니 다.형식 디 테 일 은 한 파일 이 여러 페이지 로 나 뉘 어 져 있다.첫 페이지 는 페이지 1,두 페이지 는 페이지 2,한 번 유추 라 고 한다.페이지 의 개 수 는 0 으로 페이지 가 없다 는 것 을 나타 낸다.페이지 의 크기 는 512 에서 65536 까지 가능 하 다.각 페이지 나 btree 페이지,혹은 freelist 페이지,혹은 넘 치 는 페이지.첫 페이지 는 틀림없이 btree 페이지 일 것 이다.첫 페이지 의 앞 에 있 는 100 개의 바이트 에는 특수 한 첫 번 째(파일 헤더)가 포함 되 어 있 습 니 다.이것 은 이 파일 의 설명 입 니 다.파일 헤더 의 개 수 는 다음 과 같 습 니 다.**OFFSET SIZE DESCRIPTION**0 16 Header string(첫 번 째 문자열):"SQLite format 3\\000"**16 2 Page size in bytes(페이지 의 바이트 수).**18 1 File format write version(파일 쓰기 작업 버 전)**19 1 File format read version(파일 읽 기 작업 버 전)**20 1 Bytes of unused space at the end of each page(각 페이지 끝 에 사용 되 지 않 는 바이트)**21 1 Max embedded payload fraction(최대 유효 부하 분할 삽입)**22 1 Min embedded payload fraction(최소 유효 부하 분할 삽입)**23 1 Min leaf payload fraction(최소 페이지 유효 부하 분할)**24 4 File change counter(파일 변화 카운터)**28 4 Reserved for futureuse(보존 바이트)**324 First freelist page(첫 번 째 freelist 페이지)**364 Number of freelist pages in the file(이 파일 에서 freelist 페이지 의 개수)**40 60 15 4-byte meta values passed to higher layers()**모든 정 수 는 대단 합 니 다.파일 을 수정 할 때마다 파일 변경 카운터 가 증가 합 니 다.이 계산 기 는 다른 프로 세 스 가 언제 파일 이 수정 되 었 는 지,그들의 cache 가 정리 해 야 하 는 지 알 수 있 습 니 다.최대 삽입 유효 부하 분 편 은 한 페이지 의 모든 사용 가능 한 공간 으로 표준 B-tree(비 엽 데이터)표 의 단독 사용 가능 한 총량 입 니 다.255 는 100%를 의미 합 니 다.기본적으로 한 칸(cell)의 최 대량 은 최소 4 칸 이 있어 야 한 페이지 를 채 울 수 있 는 것 으로 제한 된다.따라서 기본 적 인 최대 삽입 부하 분 편 은 64 이다.만약 한 페이지 의 유효 부하 가 최대 유효 부하 보다 크다 면 나머지 데 이 터 는 넘 치 는 페이지 에 저 장 될 것 이다.넘 치 는 페이지 가 할당 되면 많은 데이터 가 이 넘 치 는 페이지 로 옮 겨 질 수 있 지만,격자 cell 의 크기 가 최소 로 유효 부하 분 편 을 끼 워 넣 는 것 보다 작 지 는 않 을 것 입 니 다.최소 페이지 의 유효 부하 분 편 은 최소 삽입 유효 부하 분 편 과 유사 하지만 LEAFDATA tree 에 사용 되 는 잎 노드 입 니 다.LEAFDATA 의 최대 유효 부 하 는 100%(또는 값 255)로 나 뉘 어 있 으 며,첫 번 째 로 지정 하지 않 아 도 됩 니 다.BTree 의 각 페이지 는 첫 부분,칸(cell)포인터 배열,칸 cell 의 내용 으로 세 부분 으로 나 뉜 다.페이지 1 은 페이지 첫 부분 에 100 바이트 의 파일 헤더 도 있 습 니 다.file header | 100 bytes. Page 1 only. ** |----------------| ** | page header | 8 bytes for leaves. 12 bytes for interior nodes ** |----------------| ** | cell pointer | | 2 bytes per cell. Sorted order. ** | array | | Grows downward ** | | v ** |----------------| ** | unallocated | ** | space | ** |----------------| ^ Grows upwards ** | cell content||임의의 순서 가 freeblocks 와 교차 합 니 다.**|area|및 free space fragments.8:leaf**12 byte offset to the first freeblock**3 2 number of cells on this page**52 first byte of the cell content area**7 1 number of fragmented free bytes**8 4 Right child(the Ptr(N)value).Omitted on leaves.**표지 위 치 는 이 BTree 페이지 의 형식 을 정의 합 니 다.잎 leaf 표 지 는 이 페이지 에 아이 가 없다 는 것 을 의미한다.zerodata 0 데 이 터 는 이 페이지 에 key 만 포함 되 어 있 고 데이터 가 없다 는 것 을 나타 낸다.intkey 표 지 는 key 가 하나의 정수 이 고 격자 cell 의 첫 번 째 key 크기 에 저 장 된 것 이지 유효 부하 구역 에 저 장 된 것 이 아 닙 니 다.셀 포인터 배열 은 페이지 의 첫 부분 부터 시작 합 니 다.셀 포인터 그룹 은 0 개 또는 2 개의 바이트 가 남 은 숫자 를 포함 하고 있 으 며,이 숫자 는 셀 내용 영역의 셀 내용 이 파일 시작 위치의 편 이 량 을 나타 낸다.셀 포인터 식 질서 있 는.시스템 은 마지막 칸 셀 포인터 에 남 은 공간 을 확보 한 후에 새로운 칸 셀 이 페이지 를 다시 정리 하지 않 고 빠르게 추가 할 수 있 도록 합 니 다.칸 셀 내용 은 페이지 의 끝 에 저장 되 어 있 으 며 파일 의 시작 방향 으로 증가 합 니 다.격 cell 콘 텐 츠 영역 에서 사용 되 지 않 은 공간 이 링크 freeblocks 에 수집 되 었 습 니 다.프 리 블록 마다 최소 4 개의 바이트 가 있다.첫 번 째 freeblock 의 오프셋 은 페이지 첫 부분 에 나 타 났 다.프 리 블록 은 증 서 된 것 이다.하나의 freeblock 은 최소 4 개의 바이트 가 있 기 때문에 모든 격자 cell 콘 텐 츠 구역 의 3 개 또는 그 렇 군요.3 개의 사용 되 지 않 은 공간 은 freeblock 링크 에 존재 할 수 없습니다.세 개 이상 의 빈 공간 을 조각 이 라 고 한다.모든 조각의 총 개 수 를 기록 하여 페이지 의 첫 번 째 부분 에 저 장 된 오프셋 7 의 위치 입 니 다.**SIZE DESCRIPTION**2 Byte offset of the next freeblock**2 Bytes in this freeblock**격자 cell 은 가 변 길이 입 니 다.칸 셀 은 페이지 의 끝 칸 셀 내용 영역 에 저 장 됩 니 다.격자 셀 을 가리 키 는 cell 포인터 배열 은 페이지 의 첫 번 째 부분 뒤에 바짝 붙 어 있다.격자 셀 은 연속 적 이거 나 질서 가 있 을 필 요 는 없 지만 격자 셀 지침 은 연속 적 이 고 질서 가 있 습 니 다.칸 셀 내용 은 가 변 길이 정 수 를 충분히 이용 했다.가 변 길이 정 수 는 1 부터 9 개의 바이트 로 바이트 당 7 비트 가 낮 게 사용 된다.전체 정 수 는 8 자리 바이트 로 이 루어 져 있 으 며,그 중 첫 번 째 바이트 의 8 위 는 0 이다.정수 에서 가장 중요 한 바이트 가 첫 번 째 에 나타난다.가 변 길이 의 정 수 는 일반적으로 9 바이트 보다 많 지 않다.9 번 째 바이트 의 모든 8 개의 바이트 가 데이터 로 여 겨 지 는 특수 한 상황 이다.64 비트 정수 가 9 바이트 로 인 코딩 될 수 있 습 니 다.**0x 00 becomes 0x00000000**0x7f becomes 0x0000007f**0x 81 0x 00 becomes 0x00000080**0x 82 0x 00 becomes 0x000000100***0x 80 0x7f becomes 0x0000007f**0x8a 0x 91 0xd 1 0x 78 becomes 0x 12345678***0x 81 0x 81 0x 81 0x 81 0x 81 0x 81 0x 01 becomes 0x 10204081 이 글 은 리 눅 스 공사 홈 페이지(www.linuxidc.com)원문 링크 에서 유래 되 었 습 니 다.http://www.linuxidc.com/Linux/2012-11/75009.htm