태양 만세!

Linux 스터티 실습환경 구축

리눅스 배포판 : CentOS 5.11 32bit, 64bit 모두 필요함

- 가상머신 : virtualbox or vmware

- 터미널 프로그램 : xshell, xftp .

1. x86용 CentOS5.11 iso 다운받는 곳

x86 접속경로 : http://ftp.daumkakao.com/centos/5.11/isos/i386/

다운로드 파일 :

CentOS-5.11-i386-bin-DVD-1of2.iso

CentOS-5.11-i386-bin-DVD-2of2.iso

CentOS-5.11-i386-netinstall.iso

2. x86_64용 CentOS5.11 iso 다운받는 곳

접속경로 : http://ftp.daumkakao.com/centos/5.11/isos/x86_64/

다운로드 파일 :

CentOS-5.11-x86_64-bin-DVD-1of2.iso

CentOS-5.11-x86_64-bin-DVD-2of2.iso

CentOS-5.11-x86_64-netinstall.iso

3. 터미널 프로그램 다운받는 곳

접속경로 : http://www.netsarang.co.kr

다운로드 파일 : xshell, xftp

4. 가상머신 다운받는 곳

virtualbox : http://virtualbox.org

vmware : http://vmware.com

5. 오라클 11g XE 다운받는 곳

http://www.oracle.com/technetwork/database/database-technologies/express-edition/downloads/index.html

다운로드 파일 :

Oracle Database Express Edition 11g Release 2 for Linux x64

Win + 숫자 : 작업표시줄 프로그램 실행    

Win + D : 바탕화면 보기   

Win + L : 화면 잠금    

Win + E : 탐색기 실행    

Win + Home : 현재 사용 중인 창만 제외하고 모두 내림    

Win + ↑ : 현재 창을 최대화    

Win + ↓ : 현재 창을 작업표시줄로 내림

Win + ←, → : 현재 창을 화면의 왼쪽, 오른쪽 절반으로 조정  

Alt + Tab : 프로그램 전환    

Ctrl + Tab : 브라우저 창간 이동

Alt + Print Screen : 현재 창만 캡처

Ctrl + W : 현재 탭만 닫기    

Ctrl + Shift + T : 닫은 탭 다시 열기    

Shift + 다시시작 : 재부팅시 부팅옵션 표시 (windows 8 이상)

• 인덱싱과 해싱 II

  10.1 B-트리 인덱스

• B-트리 인덱스
  • B+-트리의 원형
  • B-트리와 B+-트리의 차이점
    • 단말 노드의 검색키가 비단말 노드에 중복되어 삽입되지 않음
    • 리프 노드의 모든 검색키와 레코드가 순차적으로 정렬되고 연결되어 있지 않음

         

  • 비단말 노드의 구조

    

       

    

10.2 정적 해싱과 동적 해싱

• 해싱의 개념

  검색키 값에 직접 산술적인 연산을 적용하여 데이터가 저장되어 있는 버킷의 주소를 계산하여 데이터에 접근하는 방법

  • 해시 함수 : 검색키 값을 입력하면, 레코드에 대한 디스크 블록 주소(버킷)를 반환하는 함수
  • 버킷
    • 해시 파일 구조에서 사용하는 한 개 이상의 레코드를 저장할 수 있는 공간의 단위
    • 일반적으로 버킷 하나가 디스크 블록 하나를 나타내지만 크기 조정이 가능함

      

• 정적 해싱
  • 정적 해싱: 저장 공간의 단위인 버킷 개수가 고정된 기법

       

  • 정적 해싱에서 키값이 𝑘𝑖인 레코드 삽입
    • ℎ𝐾𝑖을 통하여 𝐾𝑖에 대응하는 버킷 주소를 구함
    • 레코드를 해당 버킷에 저장

         

  • 정적 해싱에서의 레코드 탐색
    • ℎ𝐾3=hK7= 𝑗 인 경우
    • 두 레코드 모두 같은 버킷에 있으므로 𝑗 번 버킷안의 모든 레코드를 탐색하여 선택하는 과정이 필요

         

• 해시 함수
  • 충돌: 서로 다른 레코드가 동일한 버킷에 대응되는 경우
  • 동거자: 같은 버킷 주소를 갖는 레코드들
  • 오버플로
    • 버킷에 레코드를 저장할 수 있는 여유 공간이 없을 때 발생
    • 주로 별개의 버킷을 할당하여 처리
    • 오버플로는 많이 발생할수록 레코드 접근시간이 길어지고 성능이 저하

         

    

     

• 동적 해싱
  • 정적 해싱의 문제점
    • 데이터베이스의 크기가 커짐에 따른 성능 감소
    • 미리 큰 공간을 잡을 경우 초기에 상당한 양의 공간이 낭비
    • 재구성 시 새로운 해시 함수를 선택하면 모든 레코드에 대하여 다시 계산하고 버킷에 할당하는 비용이 발생
  • 동적 해싱: 버킷의 개수가 데이터베이스의 크기에 따라 변경되는 기법

       

• 확장성 해싱
  • 데이터베이스의 증대 혹은 축소에 따른 인덱스의 구조를 조절하기 위해 해시 함수의 동적 변경을 허용하는 기술
  • 디렉터리와 버킷으로 구성된 2단계 구조
    • 디렉터리는 디스크에 저장되는 버킷 주소 테이블
    • 디렉터리 깊이를 의미하는 정수값 d를 포함하는 헤더와 데이터가 저장된 버킷에 대한 2^d개의 포인터로 구성
  • 모조키(pseudo key)
    • 레코드의 키 값을 일정 길이와 비트 스트링으로 변환한 것
    • 모조키의 첫 d 비트를 사용하여 디렉터리에 접근
  • 버킷 헤더
    • 정수값 𝑖(≤𝑑)가 저장되어 있음을 표시
    • –𝑖는 버킷에 저장되어 있는 레코드의 모조키들이 처음부터 𝑖 비트까지 일치함을 표시

         

      

         

  • 레코드 삽입에 의해 분할된 확장성 해싱 파일

       

    

       

  10.3 비트맵 인덱스

• 비트맵 인덱스
  • 다중키를 가진 질의를 효율적으로 처리하기 위해 고안된 특수한 형태의 인덱스
  • 비트맵
    • 간단한 비트의 배열
    • 릴레이션 𝑟의 속성 𝐴 에 대한 비트맵 인덱스는 𝐴가 가질 수 있는 값에 대해 비트맵을 구성
    • 각 비트맵은 릴레이션에 있는 레코드 수 n개 만큼의 비트로 표현
  • 𝑖 번째 레코드가 속성 𝐴에 대해 해당 속성값을 가지면 비트맵의 𝑖 번째 비트를 1로, 그렇지 않으면 0으로 설정

    

• 비트맵 인덱스의 사용 예
  • 성별이 남자이고 성적이 B인 학생의 정보를 출력

    => SELECT *FROM 학생

    WHERE 성별='남자' AND 성적='B'

       

  • 성별의 '남자'와 성적의 'B'의 비트열에 대한 비트 논리곱 연산을 수행

    => 성별 남자 1 0 0 1 0 1

    &

    성적B 1 0 0 1 0 0

    1 0 0 1 0 0

       

    

       

  • 비트맵의 활용
    • 속성에 대한 값이 유한하고 범위가 비교적 작은 규모일 때 용이

      Ex) 직책, 학과, 혈액형 등

  • 비트맵 인덱스의 크기
    • 실제 렐레이션 크기에 비해 자유로움
    • 레코드의 길이가 수백 바이트가 되어도 바이트 인덱스에서는 하나의 비트로 표시

1. 병행 프로세스 I

   4.1 병행 프로세스

• 병행성
  • 병행성(concurrency)
    • 여러 개의 프로세스 또는 쓰레드가 동시에 실행되는 시스템의 특정

      

• 병행 프로세스의 실행 상태
  • CPU 개수에 따른 병행 프로세스의 실행 형태
    • 하나의 CPU에서 인터리빙 형식으로 실행

      

         

    • 여러 개의 CPU에서 병렬 처리 형식으로 실행

      

     

  • 메모리 구조에 따른 병행 프로세스의 실행 형태
    • 강결합 멀티프로세서 시스템-공유 메모리 구조

      

         

    • 약결합 멀티프로세서 시스템-분산 메모리 구조

      

     

• 병행성 문제
  • 병행성 프로세스들이 상호작용하는 경우 발생
    • 공유자원 점유 문제
    • 동기화 문제
    • 통신 문제

         

  • 상황에 따른 구분
    • 단일 프로세스 내의 병행성
    • 프로세스 간의 병행성

         

• 단일 프로세스 내의 병행성
  • 우선순위 그래프

    

       

  • Fork/Join 구조
    • Fork L : 2개의 병행 수행을 만듦(레이블 L위치부터와 fork 명령어 다음부터)
    • Join n : 병행하는 n개의 흐름을 하나로 재결합

      

         

      

         

  • 병행문
    • 1개의 프로세스가 여러 가닥의 병렬 프로세스로 분할 되었다가 다시 하나로 결합
    • Parbegin / parend 문

      

         

      

• 프로세스 간의 병행성
  • 비동기 병행 프로세스

    

       

    

     

     

  4.2 동기화와 임계영역

• 동기화와 임계영역
  • 프로세스 동기화
    • 2개 이상의 프로세스에 대한 처리순서를 결정하는 것

      Ex) 동시에 사용할 수 없는 공유자원,

      한 프로세스의 처리 결과에 따라 다른 프로세스의 처리가 영향을 받는 경우

  • 임계영역
    • 2개 이상의 프로세스가 동시에 액세스하면 안 되는 공유자원을 액세스하는 코드 영역
  • 상호배제
    • 2개 이상의 프로세스가 동시에 임계영역에 진입하지 못하도록 하는 것

         

• 임계 영역의 예
  • 상호배제를 통한 프로세스 동기화

    

• 임계 영역을 갖는 프로세스의 일반적 구조

  

• 임계 영역 문제해결을 위한 요구조건
  • 상호배제
    • 한 프로세스가 임계영역에서 실행 중일 때, 다른 어떤 프로세스도 임계영역에서 실행될 수 없음
  • 진행
    • 임계영역에서 실행 중인 프로세스가 없고 여러 프로세스가 임계 영역에 진입하고자 할 때 그 중에서 적절히 한 프로세스를 결정해야 하며 이 결정은 무한정 미룰 수 없음
  • 제한된 대기
    • 한 프로세스가 임계영역 진입 요청을 한 후 수락될 때까지

      다른 프로세스가 임계영역 진입을 허가 받는 횟수는 제한이 있어야 함

         

• 임계영역 문제해결을 위한 도구
  • Test-and-Set
  • 세마포어

       

• Test-and-Set
  • Test-and-Set 명령어(TS 명령어)
    • 상호배제의 하드웨어적 해결 방법
    • 분리가 불가능한 단일 기계 명령어(원자적으로 수행)

    

       

  • 상호배제의 구현

    

       

    

  • 문제점
    • 많은 프로세스가 임계영역에 들어가기를 원할 때 기아가 발생할 수 있음
    • Busy waiting을 함으로써 다른 작업이 사용할 수 있는 CPU 사이클을 낭비

      *기아(starvation)

      프로세스가 필요한 자원할당을 받지 못하고 계속적으로 대기하게 되는 상황

• 세마포어
  • 세마포어(semaphore)
    • Dijkstra가 제안한 동기화 도구
    • 세마포어 s : 사용가능한 자원의 수 또는 잠김/열림 등의 상태를 나타내는 값을 저장하는 정수형 공용변수
    • 세마포어 s는 두 표준단위 연산 P와 V에 의해서만 접근됨

         

    

• 상호배제의 구현

  

     

  

     

  

     

  

     

  

• 동기화 문제 해결
  • 프로세스1이 문장 S1을 실행한 후 프로세스2가 문장 S2를 실행하도록 동기화(block/wakeup 프로토콜)

  

1. 인덱싱과 해싱 I

   9.1 인덱싱

• 인덱싱이란?
  • 인덱싱은 데이터 검색에서 발생하는 비효율적인 문제를 해결하기 위한 기법
    • 인덱스: DBMS에서 요청된 레코드에 빠르게 접근할 수 있도록 하는 데이터와 관련된 부가적인 구조
    • 인덱싱: 인덱스를 디자인하고 생성하는 작업
  • DMBS는 인덱스를 통하여 레코드가 디스크 저장장치 또는 메모리의 어느 블록에 저장되어 있는지 파악하고, 해당 블록을 읽어 들임
    • 검색키: 파일에서 레코드를 찾는데 사용되는 컬럼이나 컬럼의 집합

         

• 인덱스의 종류
  • 순서 인덱스: 특정 값에 대해 정렬된 순서 구조
  • 해시 인덱스: 버킷의 범위 안에서 값의 균일한 분포에 기초한 구조로 해시 함수가 어떤 값이 어떤 버킷에 해당되는지 결정

       

• 인덱스의 평가기준
  • 접근시간: 데이터를 찾는 데 걸리는 시간
  • 유지비용: 새로운 데이터 삽입 및 기존 데이터 삭제연산으로 인한 인덱스 구조 갱신 비용
  • 공간비용: 인덱스 구조에 의해 사용되는 부가적인 공간비용

       

9.2 순서 인덱스

• 순서 인덱스
  • 검색키로 정렬된 순차파일에 대하여 레코드에 대한 빠른 접근이 가능하도록 순서 인덱스를 사용
    • 검색키를 정렬하여 해당 검색키와 관련된 레코드와의 연계를 통하여 인덱스 생성
• 인덱스 엔트리의 구조

포인터: 검색키에 대응되는 한 개 이상의 레코드에 대한 포인터로, 레코드가 저장되어 있는 디스크블록의 식별자와

블록 안에서 레코드를 인식하기 위한 오프셋으로 구성

• 순서 인덱스의 분류
  • 밀집(dense) 인덱스
  • 희소(sparse) 인덱스
• 밀집 인덱스
  • 모든 레코드에 대해 [ 검색키 값 | 포인터 쌍 ] 을 유지

    

  • 인덱스의 엔트리가 소수의 검색키 값만을 유지

    

• 다단계 인덱스
  • 4KB 크기의 한 블록에 100개의 엔트리가 들어간면, 100,000,000 개의 레코드의 인덱스를 유지
    • 100,000,000ro의 블록 = 4GB의 공간
    • 인덱스의 용량이 작아 전체가 메모리에 적재되면 탐색시간이 축소
    • 인덱스가 메모리보다 크다면 저장된 블록을 디스크로부터 읽어야하기 때문에 I/O 비용이 증가하여 탐색시간 증가

      => 다단계 인덱스를 구성하여 해결

  • 내부 인덱스와 외부 인덱스로 구성
    • 외부 인덱스를 내부 인덱스보다 희소한 인덱스로 구성하여 엔트리의 포인터가 내부 인덱스 블록을 지칭
    • 포인터가 가리키는 블록을 스캔하여 원하는 레코드보다 작거나 같은 검색키 값 중에 가장 큰 값을 가지는 레코드를 찾음
  • 내부 인덱스는 1,000,000 개의 블록을 갖고, 외부 인덱스는 100개의 블록만 사용하여 40MB의 외부 인덱스는 메모리에 적재가능

    

9.3 B+_트리 인덱스

• B+_트리 인덱스
  • 루트 노드로부터 모든 단말 노드에 이르는 경로의 길이가 같은 높이 균형 트리
    • 순서 인덱스는 파일이 커질수록 데이터 탐색에 있어서 접근 비용이 커지는 문제점을 해결하기 위해 제안
    • 현재까지도 널리 사용되는 대표적인 순서 인덱스

         

  • B+_트리의 노드 구조

    

     

• B+_트리 구성
  • 인덱스 세트: 단말이 아닌 노드로 구성
    • 단말 노드에 있는 검색키 값을 신속하게 찾아갈 수 있도록 경로를 제공하는 목적으로 사용
    • [n/2], n 사이의 자식을 가짐
  • 순차 세트: 단말 노드로 구성
    • 모든 노드가 순차적으로 서로 연결
  • 단말 노드의 예

    

       

• 

     

• B+_트리의 특징
  • 루트는 2, 혹은 𝑛/2~𝑛개 사이의 포인터를 가짐
  • 루트와 단말 노드를 제외한 모든 노드는 최소 𝑛/2 에서 𝑛개 사이의 포인터를 가짐
  • 모든 단말 노드는 루트로부터 같은 거리
  • 단말 노드가 아닌 노드에 있는 검색키 값의 수는 그 노드의 포인터 수보다 하나 적음
  • 단말 노드는 데이터 파일의 순차 세트를 나타내며 모두 리스트로 연결
  • 단말 노드는 적어도 (𝑛−1)/2 개의 검색키 값을 포함

       

• B+_트리 상에서의 검색
  • V=검색키, 현재 방문한 노드 = N
    • 𝑁을 조사하여 𝑉값과 같거나 𝑉보다 큰 검색키 중 가장 작은 𝐾𝑖를 찾음
    • 𝐾𝑖=𝑉이면 𝑃𝑖+1이 가리키는 노드를 방문함 (𝑁=𝑃𝑖+1)
    • 𝐾𝑖>𝑉 이면 𝑃𝑖 이 가리키는 노드를 방문함 (𝑁=𝑃𝑖)
    • 𝑉>𝐾𝑚−1 이면, 마지막 포인터 𝑃𝑚이 가리키는 노드를 방문함 (𝑁=𝑃𝑚)
    • 변경된 𝑁이 단말 노드가 아니라면, 단말 노드가 될 때까지 이전 과정을 반복
    • 𝑁이 단말 노드라면

      𝐾𝑖=𝑉이면 𝑃𝑖이 가리키는 레코드를 읽음

      𝐾𝑖와 같은 𝑉 가 없다면 𝑉를 가지는 레코드는 존재하지 않음

     

• B+_트리 상에서의 검색 예

  => '장보고' 검색

  

     

• B+_트리 상에서의 삽입과 삭제
  • 삽입: 검색과 같은 방법을 사용하여 삽입되는 레코드의 검색키 값이 속할 단말 노드를 찾음
    • 해당 단말 노드에 <검색키 값, 포인터> 쌍을 삽입
    • 삽입 시 검색키가 순서를 유지
  • 삭제: 삭제될 레코드의 검색키를 통해 삭제될 검색키와 포인터를 포함한 단말 노드를 찾음
    • 같은 검색 키 값을 가지는 다중 엔트리가 존재할 경우, 삭제될 레코드를 가리키는 엔트리를 찾을 때까지 탐색 후 단말 노드에서 제거
    • 단말 노드에서 제거된 엔트리의 오른쪽에 있는 엔트리들은 빈 공간이 없도록 왼쪽으로 이동

         

• 노드가 분할되는 삽입

  =>'강감찬' 삽입

  

     

     

  

  • 강감찬을 삽입하고자 하는 노드에 더 이상 저장할 공간이 없으므로 노드를 위 그림과 같이 분할
    • 강감찬과 김영희를 하나의 단말 노드로 구성
    • 나태양과 도철수가 하나의 단말 노드로 구성

         

    

    • 새로 만들어진 단말 노드의 가장 작은 검색키 값을 가진 '나태양'은 부모 노드에 공간이 존재하기 때문에

      추가적인 노드 분할 없이 새로운 노드를 가리키는 포인터를 삽입

• B+_트리 상에서 노드가 병합되는 삭제
  • 강감찬이 추가된 B+트리에서 피천득 삭제
    • 피천득이 있는 단말 노드를 검색

      해당 단말 노드는 삭제 후 홍길동만 남게 됨

      (𝑛−1)/2 개 보다 적은 검색키 값이 적으므로 다른 노드와의 병합이 필요

         

    • 홍길동이 저장된 노드의 왼쪽의 형제 노드와 병합

      홍길동을 포함한 엔트리를 형제 노드로 이동

      비워진 노드를 삭제

      비워진 노드를 가리키는 포인터도 삭제

      기존의 포인터를 대체할 '정도전＇을 부모 노드에 삽입

         

  • '피천득' 삭제 결과