2019-05-29.

Slides:



Advertisements
Similar presentations
비즈쿨 - 정 성 욱 - - 금오공고 비즈쿨 - 정 성 욱 1. 나는 각 단원들의 활동들에 성실하게 참여 하겠습니다. 우리의 다짐 2. 나는 나와 전체의 발전을 위해 각 멘토들의 지도에 순종하겠습니다. 3. 나는 각 단원들을 숙지함으로써 비즈니스 마인드를 함양하고 자신의.
Advertisements

노인복지론 담당교수 : 최 병태 교수님 학과 : 보건복지경영학과 학번 : 이름 : 김 태인 날짜 :
1. 시설관리공단 상임이사 정수기준을 위반한 초과 여부에 대한 질의 2. 졸속사업으로 인한 예산낭비에 대한 질의 (KT 도로개설, 강변역 고구려역사 ]
Copyright © 2014 Oracle and/or its affiliates. All rights reserved. | HR Trend & Customer’s HR Issue address OracleDirect Sales Consulting Jan 2015 고객사.
우리 ! 어디가 ? 가족 여행 정보 앱. 요약 년 국내관광 소비액은 24 조원으로 관광에 시장은 계속 커지고 있으며, 가족 여행도 늘어나고 있는 추세이다. 2. 주 5 일제시행, 여가 활동에 대한 관심 증가, “ 아빠 ! 어디가 ?”,”1 박 2 일 ” 과.
작 성 일 : 기업체명 : 주식회사 전음정밀 홈페이지 : www. 전음정밀.kr. CEO & PRESIDENT 윤금백 ESTABLISHED ( 설립일 ) Apr CAPITAL ( 자본금 ) 2 억 ( 월 재무재표기준 ) EMPLOYEE ( 직원수.
2014년도 주요법령 개정사항 (월) ~ (금) 대한전문건설협회 강원도회.
2014년 세나뚜스 평의원 연수 광주 중재자이신 마리아세나뚜스.
밥상의 희로애락 제 5 강 욕망의 밥상 - 탐식 GOOD JOB 식사하셨나요?.
효과적인 면접 준비 청주종합고용지원센터.
Ⅰ 원가회계의 개념.
Chapter 1. 운영체제의 개요 이태호.
미국경제의 신용위기가 한국경제에 미치는 영향
4. 데이터 기능 유형.
2. 일과 여가 일과 직업 1.
가족상담 및 치료.
2017 북부문화사업단 공모지원사업 교부·정산 설명회.
Chapter 5 SQL: 확장된 질의, 주장, 트리거, 뷰.
SELECT 문 사원 테이블의 모든 정보를 출력하는 예제 1. 비교 연산자 SELECT 문의 형태
화면(UI) 기반 도메인모델 작성 2014년 8월.
6장. 물리적 데이터베이스 설계 물리적 데이터베이스 설계
Chapter 16 데이터베이스 파일 인덱싱 기법, B-트리 및 B+-트리
7장 인덱스된 순차 화일.
프리젠테이션 활용 및 데이터활용 Chapter 6 인쇄 미리 보기와 인쇄 김 정 석
제 3 장 관계 데이타 모델과 관계 데이타베이스 제약조건
1. 병원 직원들을 위한 서비스기본 과정 ■ 교육 목적 ■ 교육 내용 ▪ 의료 환경 변화의 이해와 고객만족 서비스 마인드 함양
8月 환경 녹색활동의 경영성과 (주)KOFAS 항목 2012년실적(MJ) 전년도실적 13年목표 목표 1월 2월 3월 4월 5월
제 7 장 엔터티-관계를 사용한 개념적 데이타 모델링
pl x pr pl pr pl pr pr pl 피벗 이하 피벗 이상
중증장애인보호작업장 포항 바이오 파크 조원 : 09 김 정 연 07 박 재 범 08 권 경 욱.
제10장 파일 시스템 인터페이스(File System Interface)
4. 나라 사랑의 길 골든벨 퀴즈.
Chapter 5 화폐의 시간가치 McGraw Hill/Irwin
데이터베이스 (Databases) 과목 개요 문양세 강원대학교 IT대학 컴퓨터과학전공.
칼빈의 생애와 개혁자로의 변모 사학과 김종식.
국제의료관광 관련 법, 제도.
사회복지법제론 제4장 사회복지급여 수급권.
학교 홈페이지 U-Campus 클릭.
무역과 마케팅 전략 국제마케팅의 의의와 유형 국제마케팅 전략.
관계 데이타 모델과 관계 데이타베이스 제약조건 충북대학교 구조시스템공학과 시스템공학연구실
CHAPTER 06 청소년의 행동문화 : 폭력(따돌림), 위험행동, 참여.
미래유망직업.
광주대교구 대성동 본당 ‘사랑의 샘’ 꾸리아 소속 ‘사도의 모후pr.‘2000차주회
남아메리카 선교 김수정, 이하정 전희진, 장성경.
CHAPTER 04 파일 설계(FiLE Design).
Chapter 11. 건강가정을 위한 과제와 전망 1. 건강가정을 위한 과제 2. 건강가정의 전망과 미래를 위한 제언.
목 차 제1절 VE 개념 제2절 VE 탄생 제3절 VE 역사 제4절 VE 필요성 제5절 VE 정의 제6절 VE 대상
데이터베이스 (Database) 과목 개요 문양세 강원대학교 IT대학 컴퓨터과학전공.
(제8강) CSR 기업경영 접목 1. 중간시험에 대한 종합 정리 1-1. CSR 경영을 요구하는 시대적 흐름 1-2. CSR이란 무엇인지 학문적, 규범적, 제도적 논의 내용 1-3. CSR에 대한 전략적 접근법을 바탕으로 한 세월호 침몰관련 청해진해운의 실태 분석 1-4.
강의 프레젠테이션 현대 사회와 미디어 11강. 매스 미디어와 정치.
CHAPTER 9-1 한국의 사회복지정책 - 사회보험제도 -
일본의 실버산업 패션 비즈니스클럽.
Part 02. 파워포인트 실무와 활용.
좀처럼 최선을 다하지 않는 한국형 홍보 PR 3. 재규어 코리아 신차 발표회 사례 분석
한양인 주차정기권 신청 안내 2018년 2학기 관리처 관재팀.
Chapter 5 화폐의 시간가치 McGraw Hill/Irwin
데이터 베이스의 내부 구조.
1. 전문대학기초학습지원센터 접속하기 전문대학 기초학습지원센터 접속 접속URL : LOG-IN 클릭.
1. 전문대학기초학습지원센터 접속하기 전문대학 기초학습지원센터 접속 접속URL : LOG-IN 클릭.
1. 전문대학기초학습지원센터 접속하기 전문대학 기초학습지원센터 접속 접속URL : LOG-IN 클릭.
제 2 장 데이타베이스 시스템 개념과 아키텍처 Fundamentals of Database Systems
Java의 정석 제 7 장 객체지향개념 II-3 Java 정석 남궁성 강의
1. 행복한 삶과 직업 행복한 삶의 조건을 이해한다. 개인의 삶에서 직업이 차지하는 사회적, 경제적,
9月 환경 녹색활동의 경영성과 (주)KOFAS 항목 2012년실적(MJ) 전년도실적(원단위) 13年목표 목표 1월 2월 3월
윤성우의 열혈 C++ 프로그래밍 윤성우 저 열혈강의 C++ 프로그래밍 개정판 Chapter 02. C언어 기반의 C++ 2.
Chapter 1 인간행동의 이해와 사회복지실천
경찰학 세미나 제 5 강 경찰관직무집행법 2조 5호의 의미 신라대학교 법경찰학부 김순석.
4-1. 명령어 형식.
CHAPTER 4 관계 데이터 모델과 관계 데이터베이스 제약조건. CHAPTER 4 관계 데이터 모델과 관계 데이터베이스 제약조건.
엔티티-관계(ER) 모델을 사용한 데이터 모델링
Presentation transcript:

2019-05-29

Copyright © 2004 Ramez Elmasri and Shamkant Navathe 2019-05-29 Chapter 12 화일의 인덱스 구조 Copyright © 2004 Ramez Elmasri and Shamkant Navathe

Chapter Outline 단일-단계 순서 인덱스들의 유형 기본 인덱스 클러스터링 인덱스 보조 인덱스 다단계 인덱스 B-트리와 B+-트리를 사용하여 구현하는 동적 다단계 인덱스 다중키 인덱스

인덱스 - 접근 경로 단일 단계 인덱스는 데이터 화일내의 레코드를 효과적으로 찾도록 도와주는 보조 화일임 인덱스는 보통 화일내의 한 필드에 대해 정의된다 (여러 필드에 대해 정의될 수도 있음 인덱스는 <필드값, 레코드에 대한 주소>로 구성된 엔트리들을 저장한 화일이다. 인덱스는 화일에 대한 접근 경로(access path) 라고 불린다

인덱스 - 접근 경로 (계속) 인덱스 엔트리는 실제 레코드 크기보다 훨씬 작기 때문에, 인덱스 화일은 데이터 화일보다 훨씬 적은 디스크 블록을 차지한다. 인덱스에 대한 이진 탐색으로 데이터 화일의 해당 레코드에 대한 주소를 얻을 수 있다. 인덱스는 밀집 또는 희소 인덱스가 될 수 있다. 밀집 인덱스는 데이터 화일내의 모든 탐색 키 값 (즉, 모든 레코드)에 대한 인덱스 엔트리를 갖는다. 희소 (또는 비밀집) 인덱스는 탐색 값의 일부에 대해서만 인덱스 엔트리를 갖는다.

인덱스 - 접근 경로 (계속) 예: 주어진 데이터 화일: EMPLOYEE(NAME, SSN, ADDRESS, JOB, SAL, ... ) 데이터 화일에 대한 가정: 레코드 크기 R=150 바이트 블록 크기 B=512 바이트 레코드 개수 r=30000 레코드 얻을 수 있는 값: 블럭킹 인수 Bfr= B div R= 512 div 150= 3 레코드/블럭 화일의 블록 수 b= (r/Bfr)= (30000/3)= 10000 블럭 SSN 필드에 대한 인덱스에서, 필드 크기 VSSN=9 바이트 라고 가정하고, 레코드 포인터 크기 PR=7 바이트 라고 가정한다. 그러면: 인덱스 엔트리 크기 RI=(VSSN+ PR)=(9+7)=16 바이트 인덱스 블럭킹 인수 BfrI= B div RI= 512 div 16= 32 엔트리/블럭 인덱스 블록 수 b= (r/ BfrI)= (30000/32)= 938 블럭 이진 탐색시 접근할 블록 수 log2bI= log2938= 10 블록 이 비용은 다음의 평균 선형 탐색 비용보다 훨씬 적은 비용임: (b/2)= 30000/2= 15000 블록 접근 만약 화일의 레코드들이 정렬되어 있으면, 이에 대한 이진 탐색 비용은 다음과 같다: log2b= log230000= 15 블록 접근

단일 단계 인덱스의 유형 기본 인덱스 순서화일에 대해 정의할 수 있는 인덱스이다. 이 데이터 화일은 키 필드 순으로 정렬돼 있어야 한다. 데이터 화일의 각 블록에 대해 하나의 엔트리를 가지며, 블록 앵커라 불리는 각 블록의 첫 번째 레코드에 대한 키 필드 값을 엔트리로 갖는다. 각 블록의 마지막 레코드를 블록 앵커로 사용하는 방식을 이용할 수도 있다. 전체 탐색 값이 아니라 데이터 화일의 각 블록에 대해 하나의 엔트리 (즉, 블록의 앵커 레코드에 대한 키 값)을 가지므로, 기본 인덱스는 비밀집(희소) 인덱스이다.

그림 12.1 그림 11.7에 있는 화일의 순서키 필드에 대한 기본 인덱스

단일 단계 인덱스의 유형(계속) 클러스터링 인덱스 순서 화일에 대해 정의할 수 있다. 데이터 화일은 각 레코드에 대해 구별된 값을 갖지 않는 필드(즉, 키가 아닌 필드)에 따라 정렬된다. 해당 필드에 올 수 있는 각 값의 종류별(each distint value)로 하나의 인덱스 엔트리를 포함하며, 이 엔트리에는 그 필드 값을 가진 레코드들이 저장된 첫번째 블록에 대한 주소를 포함한다. 클러스터링 인덱스는 삽입과 삭제가 상대적으로 간단한 비밀집 인덱스의 한 예이다.

그림 12.2 EMPLOYEE 화일의 키가 아닌 필드 DEPTNUMBER에 대한 클러스터링 인덱스

그림 12.3 같은 클러스터링 필드값을 갖는 레코드들의 각 그룹을 위해 별도의 블록 클러스터를 가지는 클러스터링 인덱스

단일 단계 인덱스의 유형(계속) 보조 인덱스 보조 인덱스는 기본 접근 방법이 이미 존재하는 화일을 접근하는 보조 수단을 제공한다. 보조 인덱스는 후보 키나 모든 레코드에 대해 유일한 값을 갖는 필드 또는 중복된 값을 갖는 키가 아닌 필드에 대해 만들 수 있다. 보조 인덱스는 두 개의 필드로 구성된 순서 화일이다. 첫 번째 필드는 인덱스 필드인 데이터 화일의 비순서 필드와 같은 데이터 타입이다. 두 번째 필드는 블록 포인터이거나 레코드 포인터이다. 같은 화일에 여러 개의 보조 인덱스가 존재할 수 있다. 엔트리에는 레코드에 대한 보조키 값과 레코드가 저장되어 있는 블록 또는 레코드 자체에 대한 포인터가 있으므로, 키 필드에 대한 보조 인덱스는 밀집 인덱스이다.

그림 12.4 화일의 비순서 키 필드에 대한 밀집 보조 인덱스(블록 포인터를 갖는 경우)

그림 12.5 인덱스 엔트리들이 고정 길이이고 유일한 필드값들을 갖도록 하나의 간접 단계를 이용하여 구현된, 키가 아닌 필드에 대한 보조 인덱스(레코드 포인터를 갖는 경우)

표 12.2 인덱스 유형의 특징

다단계 인덱스 단일 단계 인덱스가 순서 화일이므로, 이 인덱스 자체에 대한 기본 인덱스를 만들 수 있다; 이 경우, 원래 인덱스 화일은 첫번째 단계 인덱스라 부르고 그 인덱스에 대한 인덱스는 두번째 단계 인덱스라 부른다. 위와 같은 과정을 반복하면 모든 엔트리를 한 블록에 저장할 수 있는 단계가 생기고, 이 단계의 블록을 최상위 단계라고 한다. 다단계 인덱스는 첫번째 단계 인덱스가 어떤 인덱스 유형(기본 인덱스, 클러스터링 인덱스, 보조 인덱스)이든지 사용할 수 있다.

그림 12.6 ISAM (Indexed Sequential Access Method) 조직과 유사한 2-단계 기본 인덱스

다단계 인덱스 이러한 다단계 인덱스는 탐색 트리 형태를 갖는다. 그러나 인덱스의 모든 단계가 순서 화일이므로, 새로운 인덱스 엔트리에 대한 삽입과 삭제가 매우 복잡하다는 문제점이 있다.

그림 12.8 서브트리에 대한 포인터를 갖는 탐색 트리의 한 노드

그림 12.9 차수가 p = 3인 탐색 트리

B-트리와 B+-트리를 사용한 동적 다단계 인덱스 이들 자료 구조들은 새로운 탐색 키의 삽입과 삭제를 효율적으로 처리할 수 있는 탐색 트리의 변형이다. B-트리와 B+-트리 자료 구조에서 각 노드는 하나의 디스크 블록을 할당하여 저장한다. 각 노드가 최소한 절반 이상 차 있도록 보장하여 저장 효율을 높일 수 있는 방식이다.

B-트리와 B+-트리를 사용한 동적 다단계 인덱스(계속) 완전히 차 있지 않는 노드에 삽입하는 것은 간단히 처리될 수 있다; 만약 노드가 차 있으면 삽입을 위해 두 노드로 분할한다. 노드 분할은 트리의 다른 단계로 파급될 수 있다. 삭제시 절반이상 차 있게 되는 노드에 대한 삭제는 간단히 처리될 수 있다. 삭제시 노드가 절반이하로 차게되면 이 노드를 이웃 노드들과 합병해야 한다.

B-트리와 B+-트리의 차이점 B-트리에서는 모든 단계의 노드들이 데이터 레코드들에 대한 포인터들을 갖는다.

그림 12.10 B-트리 구조 (a) q – 1개의 탐색값을 갖는 B-트리의 한 노드 (b) 차수 p = 3인 B-트리(삽입 순서는 8, 5, 1, 7, 3, 12, 9, 6이다.)

그림 12.11 B+-트리의 노드 (a) q – 1개의 탐색값을 갖는 내부 노드 (b) q – 1의 탑색값과 q – 1의 데이터 포인터를 가지는 B+-트리의 리프 노드

그림 12.12 p = 3이고 pleaf = 2인 B+-트리에 대한 삽입의 예

그림 12.13 B+-트리에서 삭제하는 예

다중키 인덱스 애트리뷰트들의 어떤 조합이 자주 사용되면 이런 애트리뷰트들의 조합에 의한 키 값을 이용하여 효율적인 접근을 제공할 수 있는 접근 구조를 구축하는 생성하는 것이 유용하다. 다중 속성에 대한 순서화된 인덱스 인덱스가 < A1, A2, …, An>의 애트리뷰트에서 생성되었다면 탐색키 값은 n개의 키값을 갖는 튜플(< V1, V2, ……, An>)이 된다. 튜플을 구성하는 각 키 값은 사전적(lexicographic) 순서를 갖는다. 분할 해싱 정적 외부 해싱의 확장된 형태이며, 동등 비교에만 적합하다. n개의 요소로 이루어진 키에 대해 해시 함수는 n개의 별도의 해시 주소를 갖는 결과를 생성한다. 버켓주소는 이런 주소들의 결합이다. 주소의 일부와 부합되는 적절한 버켓을 탐색하여 원하는 복합 탐색키를 찾을 수 있다. 애트리뷰트의 수를 쉽게 확장할 수 있다는 점과 각 애트리뷰트를 위한 어떤 별도의 접근 구조를 유지할 필요가 없다는 장점이 있다. 어떠한 구성 애트리뷰트에 대해서도 범위 질의를 할 수 없다는 단점이 있다.

다중키 인덱스(계속) 그리드 화일 EMPLOYEE 화일을 격자 화일로 구성 이 방법은 선형 눈금을 따라 여러 값의 그룹에 대응되는 셀들의 집합으로 사상되는 범위 질의에 특히 유용하다. 그리드 화일은 다중키 접근에 걸리는 시간을 줄일 수 있는 효율적인 방법이다. 그리드 화일은 그리드 배열 구조를 위해 많은 공간을 필요로 한다. 더욱이 동적 화일에서는 화일을 자주 재조직해야 하므로 유지보수 비용이 많이 증가한다.