8장 직접 파일.

Slides:



Advertisements
Similar presentations
아무도 대답하지 않았던 나눔에 관한 질문들 아름다운재단 10주년 기념 컨퍼런스를 다녀오며… 작성 : 이정인 사회복지사.
Advertisements

내 마음의 버 스 이천신하교회 청년부. 이름 : 한상훈 나이 : 30 살 종교 : 기독교 ( 모태신앙 ) 생활신조 : 인생은 한방 ! 로또나 사자 이상형 : 청순 가련한 모태미녀 특이사항 : 걸그룹 노래에 환장함 식스팩을 갖기엔 슬픈 몸을 타고 남.
10장. 시기별 학급경영 11조 염지수 이 슬 권용민 신해식.
일본 근세사. (1) 에도막부의 개창 ( ㄱ ) 세키가하라의 전투 (1600) - 히데요시의 사후 다섯 명의 다이로 ( 大老 ) 가운데 최대 영지 (250 만석 ) 를 보유하고 있던 도쿠가와 이에야스가 급부상. 이에 이에야스와 반목해 온 이시다 미쓰나리 ( 石田三成 ),
독서골든벨 2009 학년도 6 학년 1 학기 6-10 반. 1. 이야기 삼국유사 정대한 원효대사는 수행을 위해 떠나던 중 피곤하여 숲 속에서 잠이 들었다. 잠결에 너무 목이 마른 나머지 어디에 담겨있는 물을 맛있게 마셨나요 ?
아니마 / 아니무스 송문주 조아라. 아니마 아니마란 ? 남성의 마음속에 있는 여성적 심리 경향이 인격화 한 것. 막연한 느낌이나 기분, 예견적인 육감, 비합리적인 것에 대 한 감수성, 개인적인 사랑의 능력, 자연에 대한 감정, 그리.
대구가톨릭대학교 체육교육과 06 학번 영안중학교 체육교사 신웅섭 반갑습니다. 반야월초등학교 축구부 대륜중학교 축구부 대륜고등학교 대구가톨릭대학교 차석 입학 대구가톨릭대학교 수석 졸업 2014 년 경북중등임용 체육 차석 합격 영안중학교 체육교사 근무 소개.
2013 년 목 차 용어의 정의 위기경보 수준 국가 생물테러 대응 체계도 반 · 팀별 소방의 임무.
폭력. 폭력이란 무엇인가 우상의 눈물 물리적인 폭력 ( 최기표 ) VS 지능적인 폭력 ( 임형우, 담임선생님 )
두 손 들고 두 손 들고 찬양합니다 두 손 들고 찬양합니다 다시 오실 왕 여호와께 다시 오실 왕 여호와께 두 손 들고 찬양합니다 두 손 들고 찬양합니다 다시 오실 왕 여호와께 다시 오실 왕 여호와께 오직 주만이 나를 다스리네 오직 주만이 나를 다스리네 나 주님만을.
일장 - 1 일 24 시간 중의 명기 ( 낮 ) 의 길이 ( 밤은 암기, 낮은 명기 ) 광주기성 - 하루 중 낮의 길이의 장단에 따라 식물의 꽃눈 형성이 달라지는 현상 일장이 식물의 개화현상을 조절하는 중요한 요인 단일식물 - 단일조건에서 개화가 촉진되는 식물 장일식물.
1990 년 대의 중국 대중 음악. (1) 배경 (2) 1990 년대 대중 음악 (3) 중국, 1990 년대의 분위기는 ? - 가사를 중심으로.
2 학년 6 반 1 조 고은수 구성현 권오제 김강서.  해당 언어에 본디부터 있던 말이나 그것에 기초하여 새로 만들어진 말  어떤 고장 고유의 독특한 말  Ex) 아버지, 어머니, 하늘, 땅.
1 박 2 일 !!! 인천마장초등학교 유수아. 1 박 2 일 멤버 인기순 위 1 위 이승기 2 위 엄태웅 3 위 은지원 4 위 김종민, 이수근 ※인터넷에서 본것이기 때문에 사람에따라 서 다를 수 있다. ※
지금은 기도 하는 시간입니다 1. 송구영신예배를 위해서 2. ‘크리스마스 이브’ 행사를 준비하는 교육 기관을 위하여
석관중앙교회 5남전도회 석 관 중 앙 교 회 회원 소식 통권 05-04호 발행일 : 2005년 04월 회 장 : 장진호 집사
2014년도 교원 및 기간제교사 성과상여금 전달교육 개 회 국기에 대한 경례 - 인사말
도농교류를 통한 농촌관광 활성화 방안 작성: 한국농어촌공사 유상건.
선진 고양교육 “유아교육 행정 업무 연수” 유치원 회계실무 및 유아학비 연수 경기도고양교육청.
지역사회복지론 1조. 요양보호시설에 대해서 황성국 임재형 이동영
묵자 겸애, 비명, 비공, 상현, 상동, 천지, 명귀, 삼표 법.
내 아이를 위한 구강관리.
현대사회의 여성문제와 여성복지 3조 권경욱 강향원 황대인 변갑수 박창욱 김지현.
14주차 1교시 강화계획 [학습목표] 1. 강화계획의 정의를 안다 [학습내용] 1. 단순한 강화계획 2. 간헐적 강화 3. 복합 계획 4. 선택과 대응법칙 [사전학습] 강화계획이 일어날 수 있는 사례를 생각해본다.
제16장 원무통계 • 분석 ☞ 통계란 특정의 사실을 일정한 기준에 의하여 숫자로 표시한 것을 말한다.통계로서 활용할 수 있는 조건으로는 ① 동질성을 지녀야 하고 ② 기준이 명확하고 ③ 계속성이 지속되어야 하며 ④ 숫자로 표시하여야 한다 경영실적의.
연장근로와 야간·휴일근로 김영호 노무사 나눔 노사관계연구소 소장 연세대 일반대학원 박사 수료 고려사이버대 법학과 외래교수
I 문학의 개념과 역할 1. 문학의 개념 (1) 언어 예술로서의 문학 (2) 소통 활동으로서의 문학
고교평준화의 득과 실 김영주 이지영 최윤영.
서울지방세무사회 부가세 교육 사진클릭-자료 다운 세무사 김재우.
4. 목적론적 윤리와 의무론적 윤리 01. 경험주의와 이성주의 01. 경험주의와 이성주의 02. 결과론적 윤리와 공리주의
치매의 예방 김 은민 윤금 노인요양원 치매의.
쉽게 배우는 알고리즘 6장. 해시 테이블Hash Table.
해싱(hashing) Ref. C로 쉽게 풀어쓴 자료구조, 생능출판사, 2005.
CHAP 11: 해싱 순천향대학교 하상호.
2010년 직원연수 자료 제1차 : 4월 16일 ~ 17일 제2차 : 4월 23일 ~ 24일
마산에 대하여 만든이 : 2204 김신우, 2202 권성헌.
CHAP 11: 해싱 순천향대학교 하상호.
국가대표 생애주기교육 프로그램 참여방법 안내
개항기 조선과 동아시아 박 범 한국역사입문Ⅱ.
CHAP 11 : 해싱 C로 쉽게 풀어쓴 자료구조 생능출판사 2011.
수업 첫 날 교육B 황유미 첫 수업 계획에 대해 알아보도록 하겠습니다..
연결링크 이미지를 마일리지샵 내에 기획전으로 제작하여 오픈/노출 사이즈 가로 1000/세로 상관x 배너사이즈 가로 400
7장. 해시 테이블Hash Table.
CHAP 11 : 해싱.
CHAP 11 : 해싱.
대구의 부도심 대구의 주요축 동대구 부도심 4조 강민석 / 박성균 / 최은지/ 황재현/김예지.
C언어 응용 제 15 주 검색.
장애인단체 간담회 마스터 제목 스타일 편집 마스터 제목 스타일 편집 장애인 단체 간담회 마스터 부제목 스타일 편집
6장 마케팅 조사 박소현, 김중호, 박기찬.
한밭대학교 창업경영대학원 회계정보학과 장 광 식
사도행전 13장 22절 말씀 –아멘 다 윗 을 왕 으 로 세 우 시 고 증 언 하 여 이 르 시 되 내 가 이 새 의 아 들
빛 의 합 성 과 학 1 학년 Ⅱ. 빛 > 2. 빛의 색( 8/8 ) [초기 화면]
제 8 장 계산복잡도 개론 검색 문제 알고리즘 강의 슬라이드 8 검색 문제
법인회생/파산 제안서 해우리합동변호사사무소 사무장- 천성우.
기본 테이블세팅(로맨틱) 푸드스타일리스트 전공 김선아.
브라피팅 메뉴얼 리바이스 바디웨어
음양오행과 물리학 조 원 : 김용훈, 양범길, 박수진, 윤진희, 이경남, 박미옥, 박지선 (11조)
혼색 color mixture.
경찰행정과 세미나 결과를 공개해야한다. VS 비공개로 해야한다. 경찰의 근무성적평정 제도.
기업활력법 적용 사례 한국상장회사협의회 정 우 용 전무.
이야기 치료에 대하여 <8조 학문적 글쓰기 발표> 주희록 최은지
투썬 창업보육센터 입주안내서 투썬비아이관리전문 ㈜.
색채의 공감각 맛 음 냄새 촉감 5. 모양.
신뢰의 암호화, 블록체인과 미래직업 (3) 블록체인을 활용한 기술 직업군.
2019년도 지식재산창출지원사업 사업설명회 IDEA.
나-는 믿음으로 주 얼굴 보리니- 아침에 깰 때에 주형상에 만족하리 나주님 닮기 원하네 믿음으로 주얼굴 보리라 -
Chapter 2. 경영분석을 위한 재무제표 재무제표의 공시.
논리회로 설계 및 실험 9주차.
중국문학개론 한부와 겅건안문학 중어중국학과 ㅇ이진원 한부와 건안문학.
첨부 1. 불꽃 위치도 ※ 불꽃 발사 장소 : 수원월드컵경기장 남측 P4 주차장 뒤편 공원 (붉은색 원표시 부분)
Presentation transcript:

8장 직접 파일

 직접 화일의 개념 각 레코드를 직접 접근 키 값과 물리적 주소 사이에 예측 가능한 관계가 존재 R : 키 값 → 주소(보조 기억 장치: DASD) ┗━(사상 함수) 장점 빠른 직접 접근 → 대화식의 처리 목표 레코드 외에는 접근할 필요 없음 다른 레코드에 영향없이 검색, 삽입, 수정, 삭제 가능

▶ 직접 파일의 예 은행 온라인 시스템 고객 계좌 화일 트랜잭션 형식 트랜잭션 유형 I : 해당 계좌의 이자액 C, D : 금액, 날짜를 해당 계좌 번호의 레코드에 반영, 직접 화일에 재수록 계좌 번호 날짜 지출 예입 잔액 적요 계좌 번호 트랜잭션 번호 금액 날짜

 해싱 레코드 : 주소 해싱 함수(hashing function) 애트리뷰트(기본키) -> 화일내의 레코드 가능한 주소 공간>>실제 주소공간>레코드의 수 논리적 - 물리적 독립성 키 값들은 주소 공간에 독립적 키 값은 그대로두고 해쉬 함수만 조정 해싱 함수(hashing function) 키 공간을 주소 공간으로 사상 hash(키) -> 주소 주소 ⊂ 유효 키 공간

▶ 해싱의 특성 해싱(hashing) 레코드 검색 키에서 변환되어 나온 주소에 레코드를 저장하는 과정 키 -> 주소 -> 레코드 접근 순차화일 : 레코드 탐색시간 ∝ 레코드수 해싱 : 레코드 탐색시간 NOT ∝ 레코드수

▶ 설계 요소 버켓 크기 적재율 저장된 화일의 레코드 수 ----------------------- 버켓의 총용량 해싱 함수 화일에서 같은 주소에 포함될 수 있는 레코드 수 적재율 저장된 화일의 레코드 수 ----------------------- 버켓의 총용량 해싱 함수 주소 생성을 위한 변환 절차 오버플로우 해결 기법 버켓의 오버플로우

 버켓 크기 버켓 하나의 물리적 레코드 : 한번의 접근으로 채취 가능한 레코드수 충돌(Collision) 같은 해싱 주소를 가지는 화일의 한 구역 하나의 물리적 레코드 : 한번의 접근으로 채취 가능한 레코드수 충돌(Collision) 두개의 레코드가 동일 버켓으로 해싱 동거자(synonym) - 동일 주소로 해싱된 두 키 충돌 vs. 버켓에서의 탐색 시간

 적재 밀도(Packing Density) 화일이 full -> 논리적 접근수 증가 빈공간 증가 -> 기억장소의 비효율 홈 버켓 해싱 함수에 의해 생성된 주소 화일의 레코드 수 적재밀도 = --------------------------- 홈 버켓의 총 용량 70% 이상이면 충돌 급증

▶ 오버플로우 확률 N : 홈버켓수 C : 버켓 용량 K : 화일에 저장된 레코드 수 K 적재밀도 = ------- < 1 CN 예 : 30% 예비 화일 공간 목표 레코드 수 : 60,000 버켓 크기 : 12 홈 버켓수 = (60,000/12)·(10/7) = 7,143 -> 오버플로우 비율 : 2.13 % (뒤에 표 참조) 1,278 오버플로우 레코드에 대한 대비

▶ 예상 파일 오버플로 버켓크기 적재 밀도(%) 50 55 60 65 70 75 80 85 90 95 2 10.27 11.90 13.56 15.25 16.94 18.65 20.35 22.04 23.71 25.37 3 5.92 8.29 8.75 10.30 11.92 13.59 15.30 18.05 18.81 20.58 5 2.44 3.36 4.45 5.68 8.07 8.58 10.21 11.93 13.73 15.60 8 0.83 1.33 2.01 2.87 3.94 5.20 6.65 8.26 10.03 12 0.24 0.47 0.84 1.38 2.13 3.11 4.33 5.79 8.48 9.36 17 0.06 0.15 0.32 0.63 1.12 1.85 2.84 4.12 5.69 8.53 23 0.01 0.04 0.12 0.28 0.58 1.08 1.86 2.96 4.40 6.18 30 0.11 0.29 1.22 2.14 3.45 5.16

 해싱 함수 변환 함수 : 키 -> 버켓주소 해싱함수 계산시간 << 보조기억장치의 버켓 접근 시간 모든 주소에 대한 균일한 분포 주소 변환 과정 ① 키가 숫자가 아닌 경우 정수값(A)으로 변환 키 → A ② 변환된 정수값(A)을 주소 공간의 자리수 만큼의 정수값(B)으로 변환 A → B (균일 분포) ③ 얻어진 정수값(B)을 주소공간의 실제범위에 맞게 조정 B → 주소 ★ ② → 해싱함수

(1) 제산 잔여 해싱 주소 = 키값 mod 제수 = 키값 - 키값/ 제수 * 제수 → 0 ∼ 제수-1 제수 = 키값 - 키값/ 제수 * 제수 → 0 ∼ 제수-1 제수 직접 주소공간의 크기를 결정(0 ∼ 제수-1) 제수 > 화일의 크기 충돌 가능성이 가장 적은것으로 선택 소수 20보다 작은 소수를 인수로 갖지 않는 비소수

▶ 제산 잔여 해싱의 적재율과 성능 적재율 실제 레코드의 수 = ---------------------------------------- 적재할 수 있는 최대 레코드의 수 적당한 성능 최대허용치 0.7 ∼ 0.8의 적재율 n 레코드 -> 1.25n의 주소공간

▶ 제산 잔여 해싱 예

(2) 중간 제곱 해싱 (Mid square hashing) 7005672 → 4907 9412 1489 ┗━┛ 9412 * 0.7 = 6588 ( 0 < 주소 ≤ 7000 )

▶ 중간 제곱 해싱 예

(3) 중첩(Folding) 키 값을 주소와 같은 자리수를 가지는 몇개의 부분으로 나눔 접어서 합을 구함 예) 주소 크기(4숫자), 키값(123456789) 1 2345 6789 1 2 3 4 5 6 7 8 9 1 주소

▶ 중첩 해싱 예

(4) 숫자 분석 키 값이 되는 숫자의 분포 이용 키의 모든 자리수에 대한 빈도 테이블 주소로 사용될 숫자의 위치들을 선택 ↖ 균일한 분포(같은빈도수)

(5) Exclusive-OR 변환 Ex-OR 0  0 = 0 1  0 = 1 0  1 = 1 1  1 = 0 0  0 = 0 1  0 = 1 0  1 = 1 1  1 = 0 키의 길이가 길때 제산잔여 방법을 적용하기 전에 수행 EX-OR : procedure (arg1, arg2) Retuen((arg1 OR arg2) AND (NOT(arg1 AND arg2))); END EX-OR; Addr = EX-OR(Keypart1, Keypart2); Ex-OR('RA', 'MA') = Ex-OR('MA', 'RA')

(6) 숫자 이동 변환 ① 중앙을 양분 ② 안쪽으로 shift ③ 주소 범위에 맞도록 조정 (조정 상수) 주소 공간 : 5000 6912 * 0.5 = 3456 : 실제 주소

(7) 진수 변환 ① 키 값의 진수를 다른 진수로 변환 ② 초과하는 높은 자리수를 절단 예) 172148 : 키 값 172148 : 키 값 주소공간 : 7000 진수 : 11 1 115 + 7  114 + 2  113 + 1  112 + 4  111 + 8  110 = 266373 보정 : 6373 * 0.7 = 4461

 오버플로 해결 방법 오버플로 해결 방법 폐쇄 주소법 (체인법) 삽입할 레코드가 꽉 찬 버켓에 해싱될 때 개방 주소법 계산 접근법 탐색할 버켓의 주소를 동적으로 계산 폐쇄 주소법 (체인법) 자료구조 접근법 오버플로 버켓을 체인으로 홈 버켓에 연결

(1) 개방 주소법 선형 조사(탐색) 다음의 빈 공간을 순차적으로 탐색 Ai = f(i, 키) i = 0,1,2,... ex) Ai = (i  step + hash(키)) mod N 원하는 레코드/빈 레코드까지 조사 문제점 기본 집중 - 비선형 함수 사용 2차 집중 - 이중 해싱 사용

▶ 이중 해싱 재 해싱 첫 번째 해싱 함수의 결과에 두 번째의 해싱함수를 적용시킨다. A0 = h1(키) A1 = A0 + h2(키) mod 화일의 크기 재 해싱된 주소는 메인 화일의 주소 (또는 오버 플로우 구역)가 될 수 있다. 주의: 적재 인자(load factor)가 크다.(≒ 80%) 이중 해싱이 선형조사보다 낫다.

▶ 개방 주소법의 문제 레코드의 삭제 논리적 삭제 재해싱 삭제된 레코드를 공간으로 처리 이후의 오버플로 검색 실패 삭제 표시 이후의 레코드를 삭제후 재삽입

(2) 폐쇄 주소법 체인법 별도의 리스트 유지, 홈 버켓에서 연결 연합 리스트 디렉토리 방법 포인터 공간 문제 홈 버켓의 여분의 공간에 저장 포인터 공간 감소 검색 비용 증가 디렉토리 방법 오버플로 레코드의 키/포인터 저장

 테이블 이용 해싱 보조기억장치를 한번 접근으로 검색 각 버켓을 위한 엔트리 테이블을 주기억장치에 유지 버켓 주소와 사인 순열 키 버켓 주소 사 인 White Blue Lilac Red Green 85 87 89 91 93 … 85 86 87 88 89 … 85 90 95 0 5 … 85 92 99 6 13 … 00101 01001 10100 10111 … 00110 00011 00110 10000 … 01000 10100 11000 10100 … 00010 11000 11110 10010 … 00011 00100 10001 00111 …

▶ 테이블 이용 해싱을 이용한 삽입 버켓 주소에 따라 삽입 오버플로의 경우 버켓 크기 = 3, RED 삽입할 때 RED (사인 00010 = 2) WHITE (사인 00101 = 5) BLUE (사인 00110 = 6) LILAC (사인 01000 = 8) 분리 사인 선택 (8 선택) => 테이블 엔트리 RED, WHITE, BLUE => 버켓85 LILAC => 버켓90, 사인=20(10100)

▶ 테이블 이용 해싱을 이용한 검색 검색 키로부터 정보 생성 버켓1, 버켓2, 버켓3, ... 사인1, 사인2, 사인3, ... 다음을 만족하는 가장 작은 i 사인i < 테이블[버켓i] 검색 레코드는 버켓i에 존재

 확장성 직접 화일 레코드수의 변화가 큰 경우 해결방안 재해싱 확장성 화일 긴 시간, 재해싱 동안 접근 곤란 가상 해싱 동적 해싱 확장 해싱

(1) 가상 해싱(Virtual hashing) 여러 개의 관련된 해쉬함수 사용 제산 잔여기법 사용 N : 버켓의 수 C : 버켓 크기 h0 : 주소 = 키 mod N 오버플로우: 관련된 버켓을 분할 hj : 주소 = 키 mod (2j * N), j = 0,1,2,.... C+1개의 레코드를 재해쉬

▶ 가상 해싱(Virtual hashing) 예 N = 100, C = 5, 버켓 53 = [ 53, 353, 253, 2453, 52753] h0 : 주소 = 키 mod 100 → 새원소 23753, h1 : 주소 = 키 mod 200 버켓 53 = [53, 253, 2453] 버켓 153 = [353, 52753, 23753] 새원소 3453, 5453, 7453, h2 : 주소 = 키 mod 400 버켓 53 = [53, 2453] 버켓 253 = [253, 3453, 5453, 7453]

(2) 동적 해싱(Dynamic hashing) 해쉬된 주소로서 인덱스를 사용 두 단계의 조직 인덱스: 주 기억 장치 버켓 : 보조 저장 장치 두 개의 해쉬 함수 사용 h : 인덱스 레벨 0 B : 인덱스 레벨 > 0 분기를 결정 레코드는 인덱스의 포인터에 의해 접근됨 키 → 인덱스(1 ∼ N) 인덱스 : N개의 이진트리의 포리스트(forest) 인덱스 노드 내부노드(0, 부모, 왼쪽 자식, 오른쪽 자식) 외부노드(1, 부모, 레코드 수, 버켓 포인터)

▶ 초기의 동적 화일

▶ 버켓 분할 B함수 사용 : 키 → 이진 스트링 분할 되는 버켓이 레벨 I이면 B(키)의 I+1째 비트를 사용 ∴ 0 왼쪽(이전) 버켓 1 오른쪽(새로운) 버켓 H0와 B에 대한 예 키 H0(키) B(키) 157 2 10100 … 95 1 00011 … 88 01100 … 205 10010 … 13 10111 … 125 10001 … 6 01000 … 301 00110 …

▶ 5번의 삽입 후의 동적 화일

▶ 분할 뒤의 화일

▶ 함수 B의 구현 어떤 h1에 대해 h1: 키 → X0 Xi+1 ← (Xi * a + b) mod C Xi:정수 bi ← 패리티(Xi) 키 ↓ X0 → X1 → X2 → X3 → .... ↓ ↓ ↓ ↓ b0 b1 b2 b3 ....

(3) 확장성 해싱(Extendible hashng) 두 단계의 조직 디렉토리 : 정수 값(d)을 갖는 헤더와 리프에 대한 2d개의 포인터 리프의 집합 : 헤더를 가지는 버켓 하나의 해쉬함수 사용 h : 키 -- 모조키 (고정 길이의 비트 스트링) 리프의 헤더 : 버켓 레코드에 대한 공통 전위 비트의 개수

▶ 확장성 해싱의 검색과 삽입 검색 모조 키의 처음 d비트를 디렉토리에 대한 인덱스로 사용하여 디렉토리에서 리프를 찾아 레코드를 접근 삽입 리프를 찾아(검색과 같은 방법) 삽입 리프가 가득 찼으면 ① 새로운 리프 할당 ② 리프의 헤더가 T이면, 모조키의 T+1 번째 비트의 값에 따라 C+1개의 레코드를 분할 ③ T, d의 값에 따라 d≥T+1 : 포인터들을 분할, 이전의 리프와 새로운 리프 모두 T+1의 헤더를 가짐 d<T+1 : 디렉토리의 크기를 두 배로, d←d+1

▶ 확장성 해싱 화일

▶ 리프 분할 뒤의 화일

▶ 리프 분할 뒤의 화일