DataBase Flashcards Preview

PE > DataBase > Flashcards

Flashcards in DataBase Deck (122)
Loading flashcards...
121

해싱

▣ 정의
- 하나의 문자열을 보다 빨리 찾을 수 있도록 해시함수를 이용하여 해시테이블내 주소에 직접 접근할 수 있는 짧은 길이의 값이나 키로 변환하는 과정
▣ 목적
- 해시 테이블
- 암호화
- 데이터 축약
▣ 동작과정
1) 레코드 키 값
2) 해싱함수 처리
3) 버켓주소 지정
▣ 구성요소
- 해싱함수 : 키값과 물리주소 매핑
- 해시키 : 레코드의 키값
- 버킷 : 여러개의 슬롯으로 구성
- 슬롯 : 한 개의 레코드 저장
- 해시테이블 : 해시 주소 저장
- Synonym : 같은 버킷 주소를 갖는 레코드들의 집합
- Collsion : 서로 다른 레코드들이 같은 주소로 반환되는 경우
▣ 해시함수의 기법
- 나눗셈법 : 나머지 연산자
- 중간제곱법 : 제곱결과에서 중간의 몇 비트값
- 폴딩법 : 탐색키 전체 (이동폴딩 : 수를 더함, 경계폴딩 : 이웃 부분 뒤집어서 더함)
- 기수 변환법 : 진법 이용
- 자릿수 분석법 : 레코드 자리 분석
- 무작위 방법 : 난수
▣ 해싱의 종류
1) 정적해싱 (Static Hashing)
- 버킷 주소의 집합을 고정 처리
- 연결리스트 사용
2) 동적해싱 (Dynamic Hashing)
- 데이터의 증감에 적용하기 위해 동적으로 해시함수가 교정
▣ 해시 충돌 해결방안
1) 개방주소법(Open Addressing)
- 빈자리 탐색하여 해결
- 선형탐사, 제곱탐사, 이중해싱법, 무작위검색법
2) 체이닝(Chaining)
- 연결리스트 이용하여 해결
- 선형탐사, 제곱탐사
3) Coalesced hashing
- Chaining 과 open-addressing 혼합
- Chain이 Link 가짐
4) Rehashing
- 해시 테이블의 특정 임계점(80% 사용) 돌파하면 더 큰 테이블을 새로 만들어 데이터를 모두 옮기는 방법
▣ Open Addressing 해시 충돌 해결 방안 상세 설명
- 선형조사법 : 순차적 탐색
- 이차조사법 : 2차 함수 이용
- 이중해싱법 : 1차 충돌 발생시 2차 해시 함수 이용
- 무작위검색 : 난수사용

122

Tree

▣ B-Tree
- 루트노드는 최소한 2개의 자식노드와 적어도 한 개의 값을 가지며, 루트노드와 리프노드를 제외하고는 최소한 1/2이상이 채워져 있는 효율적인 자료구조
▣ B+Tree
- B트리의 순차탐색의 문제를 개선하기 위해 인덱스 Set과 순차 Set으로 트리를 구별하여, 데이터를 순차적으로 접근하기 용이하게 만들 자료구조
▣ R-Tree
- N차원의 공간 데이터를 효율적으로 저장하고 지리정보와 관련된 질의를 빠르게 수행할 수 있는 자료구조
▣ R+Tree
- R-Tree와 K Dimensional Tree의 중간형태로, 기본적인 자료구조와 연산은 R-Tree와 거의 동일하며, R+Tree는 내부 노드들의 중첩을 최소화 하는 방법을 제시하여 삽입이나 삭제시 연산성능이 더 우수함
▣ T Tree
- AVL Tree 의 공간낭비와 잦은 회전연산을 개선하기 위하여 B-Tree의 장점을 결합하여 MMDBMS에 적합하도록 고안된 인덱스