BEST WISH

T-tree

• AVL 트리의 이진 탐색 특성 및 높이 균형과, B트리의 업데이트와 저장효율 장점을 모두 취한 MMDB 최적 트리
• 물리주소를 직접 포인팅 → B-Tree에서 진화된 형태로 물리적인 주소의 논리적인 변환 없이 빠르게 접근 가능한 자료구조
• T- 트리에서 'T'는 노드 데이터 구조 모양을 나타낸다
• 기존의 B-Tree의 Data Page의 다단계 검색의 복잡성 극복
• 한 노드의 가장 작은 값과 가장 큰 값의 비교
• Datablitz, EXtremeDB, MySQL Cluster, Oracle TimesTen 및 MobileLite와 같은 주 메모리 데이터베이스에서 사용
• 균형이 유지되는(balanced) 데이터 구조로, 인덱스와 실제 데이터가 모두 메모리에 모두 저장되는 경우에 최적화된 구조 (디스크 I/O가 없음)
• 하드디스크와 블록지향 보조 저장장치의 저장에 최적화 된 인덱스 구조
• T- 트리는 인덱스 트리 노드 자체 내에 인덱스 된 데이터 필드의 사본(copy)을 유지하지 않으며, 실제 데이터가 항상 주 메모리에 인덱스와 함께 저장되어 실제 데이터 필드에 대한 포인터 만 포함한다는 이점을 가짐
• 단점 : 1차원 데이터에만 적용이 가능하며, 최근 매모리 기술 발전으로 B트리에 비해 성능 우위가 낮아짐 

구조도

• 해당 노드의 값보다 작은 값은 왼쪽 서브트리에 위치
• 해당 노드의 값보다 큰 값은 오른쪽 서브트리에 위치
• 노드의 구성
  1. 부모 노드에 대한 포인터
  2. 왼쪽 자식 노드
  3. 오른쪽 자식 노드
  4. 정렬 된 데이터 포인터 배열
  5. 일부 추가 제어 데이터
• 노드의 종류
  1. 내부 노드 (internal node) : 두개의 하위 트리가 있는 노드
  2. 리프 노드 (leaf node) : 두개의 하위 트리가 없는 노드
  3. 반엽 노드 (half-leaf node) : 하나의 하위 트리 만있는 노드
  4. 값의 경계 노드 (bounding node) : 값이 노드의 현재 최소값과 최대 값 사이에있는 경우 노드
• 경계 값 (Bound values) :  각 내부 노드는 리프 노드 또는 반엽 노드를 가진다. 리프노드와 반엽노드는 가장 작은 데이터 값(최대 하한 이라고 함, greatest lower bound) 보다 크고, 가장 큰 데이터 값(최소 상한 이라고 함, least upper bound) 보다 작은 값을 가진다.
• 리프 및 반엽 노드에는 데이터 배열의 최대 크기부터 최대 크기까지 다양한 수의 데이터 요소가 포함될 수 있다
• 내부 노드의 점유율(채워진 양)은 미리 정의 된 최소 및 최대 요소 수 사이에서 유지

운행 방식

• 노드의 가장 작은 값과 가장 큰 값을 검색 Value와 비교
• 삽입 시 검색 후 공간이 없으면 가장 작은 Value를 제거하고 재정렬

성능의 이점

• 업데이트와 저장의 효율 : 분리, 병합을 통한 재균형 과정이 자가 균형 이진 탐색 트리 만큼 자주 일어나지 않는다. (B 트리, 데이터의 갯수가 일정 갯수 사이라면 분리, 병합이 일어나지 않는다)
• 한 노드안에 여러개의 데이터를 가짐 (B트리 성질)
• 이진 검색, 높이 균형, 인메모리(in-memory) 트리 구조의 성능 이점을 갖음 (AVL트리) 
• 저장공간의 오버해드를 피함
• 
  

  B-트리	T-트리	AVL
  분리 및 병합을 통해 재균형 과정은 다른 자가균형 이진 탐색 트리(AVL) 만큼 자주 일어나지 않음
  	이진 탐색
  	높이 균형을 가짐
  	저장공간 오버헤드를 피함
  한 노드안에 여러개의 데이터를 가짐
  	물리적인 주소의 논리적인 변환 없이 빠르게 접근 가능
  	Data Page의 다단계 검색의 복잡성 극복

• B- 트리 (또는 B+트리)는 디스크 기반 관계형 데이터베이스 시스템에서 가장 널리 사용되는 인덱스 구조인 것과 비교할 때, T- 트리는 메인 메모리의 인덱스 구조로 널리 받아 들여졌습니다. 이는 모든 데이터 베이스(또는 대부분)가 메인 메모리에 상주하고 있기 때문이다
• T- 트리는 주 메모리 데이터베이스에 널리 사용되는 것처럼 보이지만 최근 연구에 따르면 최신 하드웨어에서는 실제로 B- 트리보다 성능이 좋지 않다.  주된 이유는 현재의 캐시 접근과 메인메모리 접근 사이의 속도 차이을 고려할때, 메모리 참조가 균일한 비용을 가진다는 전통적인 가정이 더이상 유효하지 않기 때문이다.
• 문헌에 보고된 T 트리 관련 작업은 대부분 동시통제를 고려하지 않았다. T- 트리에 대한 두 가지 동시성 제어 접근 방식이 제시된다. 시뮬레이션 연구 결과에 따르면 동시성 제어가 시행되는 경우 널리 사용되는 B- 트리 인덱스의 변형 인 B- 링크 트리가 T- 트리보다 성능이 우수하다. 이는 T- 트리에 대한 동시성 제어가 B- 링크 트리보다 많은 잠금 작업을 필요로하고 잠금 및 잠금 해제의 오버 헤드가 높기 때문이다.

<참고>

AVL 트리

• 균형잡힌(balanced) 이진 탐색 트리
• 1962년 G.M. Adelson-Belskii와 E.M.Landis의 논문을 통해 발표되었으므로, 이들의 이름을 따서 이름이 지어졌다
• 각각의 노드(node, 분기점)마다 왼쪽과 오른쪽 부분 트리(sub-tree)의 높이 차이에 대한 정보를 가지며 부분 트리의 높이 차이가 1보다 크지 않은 성질을 가진다.
• 균형 잡힌 AVL 트리는 n개의 원소가 있을 때 O(log n) 의 시간복잡도로 검색, 삽입, 삭제를 할 수 있다.
• 삽입과 삭제를 할 때에는 원하는 노드를 찾기 위해 2개의 경로가 필요하기 때문에 레드-블랙 트리만큼 효율이 좋지 않아 자주 쓰이지는 않는다.

B 트리 (Balanced, Binary, Boeing Tree)

• 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질수 잇는 자식 노드의 최대 숫자가 2보다 큰 트리구조
• 내부 노드의 자식 수가 미리 정해진 범위 내에서 변경가능 하기 때문에 항목이 삽입되거나 삭제될 때, 내부 노드는 해당 범위의 자식 노드의 수를 만족시키기 위해 분리되거나, 병합 된다.
• 자식 노드의 수가 일정 범위 내에서만 유지되면 되므로 분리 및 병합을 통해 재균형 과정은 다른 자가균형 이진 탐색 트리(AVL) 만큼 자주 일어나지 않지만, 저장 공간에서 손실은 있게 된다.
• 노드 접근시간이 노드에서의 연산시간에 비해 훨씨 길 경우 (접근시간 > 연산시간, 예를 들면 하드디스크나 2차 저장장치), 다른 구현방식에 비해 상당한 이점을 가지고 있다.
• 각 내부 노드에 있는 자식 노드의 수를 최대화함으로써, 트리의 높이는 감소하며, 균형 맞춤은 덜 일어나고, 효율은 증가하게 된다. 대개 이 값은 각 노드가 완전한 하나의 디스크 블로 혹은 2차 저장장치에서의 유사한 크기를 차지하도록 정해진다.
• 즉, 자식 노드의 수 증가  → 트리의 높이 감소 (노드 내 데이터 증가)  → 탐색시간 감소 (연산시간 증가) 

MMDB (MainMemoryDB, 메인메모리 DB) :  데이터베이스 전체를 주기억장치에 상주시킨 데이터 베이스

B-Tree의 Data Page의 다단계 검색 : 

1. 삽입 정렬 (Insert Sort)

2번째 원소부터 앞쪽의 원소들과 비교하면서 재자리를 찾아가는 방법

for(index 1 부터 전체 배열 순회) {
  insert_obj = arr[i];

  for(i-1 번째 원소부터 왼쪽으로 순회) {

    //만약 현재 원소가 삽입할 원소보다 크다면
    if(arr[j] > insert_obj) {
      //오른쪽으로 한칸 땡기면서 자리를 마련한다
      arr[j+1] = arr[j];
    }
    else {
       break;
    }
  }
  
  //마련한 자리에 삽입
  arr[j+1] = insert_obj;
}

2. 선택 정렬 (Selection Sort)

1번째 원소부터 최솟값을 찾아 자리 교환을 해나가는 방법

for(원소 전체 순회) {
  //최소값을 가진 인덱스 유지
  min_index = i;
  
  for(i+1 부터 원소 전체 순회) {
    if(최소값 보다 현재 원소가 더 작다면) {
      //최소 인덱스 교체
      min_index = j;
    }
  }

  //순회가 끝난 후 현재 원소와 최소 값을 교환
  temp = arr[i];
  arr[i] = arr[min_index];
  arr[min_index] = temp;
}

3. 버블 정렬 (Bubble Sort)

바로 옆의 원소와 비교하면서 순서가 맞지 않을 경우 교환하는 방법

for(전체 원소 순회) {
  for(1번째 원소부터 마지막에서 1개 전 원소까지 순회) {
    if(n번째와 n+1번째의 순서가 맞지 않을 경우) {
      //원소 교환
      temp = arr[j];
      arr[j] = arr[i];
      arr[i] = temp;
    }
  }
}

3. 소스 코드

package sort;

import java.util.Arrays;
import java.util.Random;

public class SortTest {

	//배열 설정 값
	private static int MAX_LEN = 12;
	private static int MAX_INT = 30;

	public static void main(String[] args) {

		SortTest me = new SortTest();

		int arr[] = me.getRandomNumberArr();

		System.out.println("정렬 전 >> " + Arrays.toString(arr));

		//1. 삽입 정렬
		int insertSortarr[] = me.InsertionSort(arr);
		System.out.println("삽입 정렬 >> " + Arrays.toString(insertSortarr));

		//2. 선택 정렬
		int selectionSortarr[] = me.InsertionSort(arr);
		System.out.println("선택 정렬 >> " + Arrays.toString(selectionSortarr));

		//2. 버블 정렬
		int bubbleSortarr[] = me.bubbleSort(arr);
		System.out.println("버블 정렬 >> " + Arrays.toString(bubbleSortarr));

	}

	/**
	 * 삽입 정렬 알고리즘
	 * @param arr
	 * @return
	 */
	int[] InsertionSort(int[] arrParam) {
		int i, j;
		int insert_obj;

		int arr[] = arrParam.clone();

		for(i=1; i<MAX_LEN; i++) {
			insert_obj = arr[i];

			for(j=i-1; j>-1; j--) {
				if(arr[j] > insert_obj) {
					//자리 마련하기
					arr[j+1] = arr[j];
				}
				else {
					break;
				}
			}
		arr[j+1] = insert_obj;
		}

		return arr;
	}

	/**
	 * 선택 정렬 알고리즘
	 * @param arr
	 * @return
	 */
	int[] selectSort(int[] arrParam) {
		int i, j;
		int min_index;
		int temp;

		int arr[] = arrParam.clone();

		for(i=0; i<MAX_LEN; i++) {
			min_index = i;
			for(j=i+1; j<MAX_LEN; j++) {
				if(arr[min_index] > arr[j]) {
					min_index = j;
				}
			}

			if(i != min_index) {
				//값 교환
				temp = arr[i];
				arr[i] = arr[min_index];
				arr[min_index] = temp;
			}

		}


		return arr;
	}

	/**
	 * 버블 정렬
	 * @param arr
	 * @return
	 */
	int[] bubbleSort(int[] arrParam) {
		int i, j;
		int temp;

		int arr[] = arrParam.clone();

		for(i=0; i<MAX_LEN; i++) {
			for(j=0; j<MAX_LEN-1; j++) {
				if(arr[i] < arr[j]) {
					temp = arr[j];
					arr[j] = arr[i];
					arr[i] = temp;
				}
			}
		}

		return arr;
	}

	/**
	 * n개의 중복 되지 않는 랜덤 배열 생성
	 * @param len
	 * @param maxNumber
	 * @return
	 */
	int[] getRandomNumberArr() {
		return getRandomNumberArr(MAX_LEN, MAX_INT);
	}

	int[] getRandomNumberArr(int len, int maxNumber) {

		long seed = System.currentTimeMillis();
		Random rand = new Random(seed);

		int arr[] = new int[len];
		int tempInt;
		boolean validIntInserted;

		if(len > maxNumber) {
			System.out.println("랜덤 배열을 만들 수 없음(배열 길이보다 최대 숫자가 큼)");
			return arr;
		}

		//랜덤 배열 생성
		for(int i=0; i<len; i++) {

			while(true) {
				validIntInserted = true;
				tempInt = rand.nextInt(maxNumber);
				for(int j=0; j<i; j++) {
					if(arr[j] == tempInt) {
						validIntInserted = false;
					}
				}
				if(validIntInserted) {
					arr[i] = tempInt;
					break;
				}
			}

		}

		return arr;

	}


}

결과

정렬 전 >> [28, 17, 1, 14, 8, 25, 4, 10, 12, 19, 13, 15]
삽입 정렬 >> [1, 4, 8, 10, 12, 13, 14, 15, 17, 19, 25, 28]
선택 정렬 >> [1, 4, 8, 10, 12, 13, 14, 15, 17, 19, 25, 28]
버블 정렬 >> [1, 4, 8, 10, 12, 13, 14, 15, 17, 19, 25, 28]

※ 동기 프로토콜과 동기 프로토콜의 차이
   : 송신자와 수신자가 데이터 전송 전에 클락을 동기화 하는지 여부가 가장 큰 차이점이다

1. 비동기 프로토콜 (asynchronous protocol)

• 비트 스트림에 있는 각 문자를 독립적으로 다룬다
• 주로 모뎀에서 사용하며, 시작과 정지 비트, 문자 사이에 가변 길이 갭을 가진다
• 각 문자는 시작과 정지 비트스를 포함한다. 문자들은 간격(gap)으로 각자를 구분된다. 헤더는 2바이트 (16비트)로 구분된다. 시퀀스 번호와 첨가한다
  
• 데이터가 바이트나 문자 형태로 송신 된다
• 이 전송은 반이중 방식이다
• 비동기 전송 방식에서는 시작 비트들(start bits)과 중지 비트들(stop bits)이 데이터에 첨가 된다. 동기화가 필요하지 않다

2. 동기 프로토콜 (synchronous Protocol)

• 전체 비트 스트림을 같은 크기의 문자들로 나누어 처리한다
• 데이터가 블록 또는 프레임 형식으로 전송된다 
• 전이중 방식이다
• 송신자와 수신사 사이에서 동기화가 필수다
• 데이터 사이의 틈(gap)이 없다
• 이 때문에 많은 양의 데이터를 전송할때, 동기 전송보다 효율적이고 신뢰성이 높다
• 빠르고, 비용이 많이 드는 방식이다
• 비트 중심, 문자 중심 프로토콜이 있다

2-1. 문자 중심 프로토콜

• 프레임 또는 패킷을 문자의 연속으로 해석한다
• 비트 중심 프로토콜보다 비효율 적이므로 오늘날 거의 사용되지 않는다
• 수신자는 8비트 (바이트 중심일 경우) 를 적절한 문자라고 생각한다.
• 오직 아스키 코드를 사용하는 프린터나, 키보드와 통신할 때 사용함
• BSC(바이너리 싱크로노우스 커뮤니케이션) 프레임 : 컨트롤 프레임, 데이터 프레임
  

2-2. 비트 중심 프로토콜

• 프레임 또는 패킷을 비트의 연속으로 해석한다
• 모든 필드는 임의의 숫자의 비트 크기로 올수 있다
• 만약 (01111110) 의 플레그를 전송하고 필요 비트들을 뒤이어 전송하고, 플레그로 다시 전송을 종료한다. 이를 통해서 임의의 길이의 비트들을 전송할 수 있다
• 비트 스터핑이 필요 : 이 때문에 플레그와 같은 데이터를 보내려면 (0이 5번 연속으로 온다면 0을 전송해야 한다) (예 01111110 -> 011111010 )
• 보다 짧은 프레임에 많은 정보를 전송한다
• 문자 중심 프로토콜에 있는 투명성 문제 해결한다
• SDLC, HDLC, LAPs, PPP
  

• MTBF
  • Mean Time Between Failure, 고장 간 평균 시간
  • 고장에서 다음 고장까지의 평균 시간을 말한다. 즉 고장이 나지 않은 평균 가동 시간
• MTTF
  • Mean Time To Failure, 평균 실패 시간
  • 수리한 후 다음 고장 까지의 평균 시간
• MTTR
  • Mean Time To Repair, 평균 수리 시간
  • 고장 발생 시점에서 수리 시까지의 평균 시간
  • MTBF = MTTF + MTTR

   

• 이용 가능성
  
  • 주어진 시점에서 프로그램이 요구에 따라 작동되고 있을 가능성
  • MTTF / (MTTF + MTTR) * 100%

결합도 : 두 모듈간의 상호 의존 성 정도

(1. 낮다 ~ 6. 높다 / 낮을수록 바람직함)

1. 데이터 결합 : 데이터를 매개 변수로 전달함으로써 두 모듈 들이 소통 (예 : 정수나 실수나 문자 등을 전달하는 것)
2. 스탬프 결합 : 레코드, 구조체 또는 객체와 같은 복합 자료를 이용하여 소통하는 경우
3. 제어결합 : 한 모듈의 데이터가 다른 모듈의 실행 순서를 결정하기 위해 전달되는 경우
4. 외부 결합 : 모듈들이 소프트웨어 외부의 환경에 좌우되는 경우 (외부에서 정한 포맷, 프로토콜 사용)
5. 공통 결합 : 전역 변수를 공유
6. 내용 결합 : 두 모듈이 코드를 공유하는 경우 (예 : 한 모듀에서 분기가 다른 모듈로 떨어지는 경우로, 한 모듈이 다른 모듈의 내부 작업을 직접 참조하는 경우)

응집력 : 하나의 모듈이 가지는 기능적 집중성에 관한 척도

(1. 높다 ~ 7.낮다 / 높을수록 바람직함)

1. 기능적 응집력 : 한 모듈을 구성하는 요소들이 단일 기능을 수행하기 위해 협력
2. 순차적 응집력 : 모듈을 구성하는 한 요소의 축력이 다음 요소의 입력이되며 순차적으로 구성
3. 통신 응집력. 모듈이 수행하는 모든 기능들이 같은 자류구조를 참조하거나 수정하는 경우. (예 : 하나의 배열이나 스택을 조작하도록 정의된 기능 집합)
4. 절차적 응집력 : 모듈이 가지는 기능들이 순서에 의해서 처리되는 경우 (예 : 한 메시지를 디코딩 하기 위해 일련의 순차적 과정을 수행하는 경우)
5. 시간적 응집력 : 같은 시간 주기에 실행되어야 하는 기능들을 개는 모듈 (예 : 초기화 또는 종료를 위한 기능들을 수행하는 모듈)
6. 논리적 응집력 : 모듈의 구성요소들이 유사한 기능을 수행하는 경우  (예 : 오류처리, 자료입력, 자료 출력 등) 
7. 우연적 응집력 : 연관성이 매우 떨어지는 작업들을 수행하는 모듈들은 우연적 응집력을 가짐

레지스터

• PC (프로그램 카운터) : 패치 해야 하는 다음 명령의 메모리주소를 포함한다
• 스택포인터 : 메모리에 있는 현 스택의 최상위를 가리킨다, 아직 종료하지않음 프로시저 별로 하나의 프레임을 갖는다
• PCW (Program Status Word) : 비교 연산자들에 의해 설정되는 조건 코드 비트들, CPU의 우선순위, 모드(사용자 또는 커널) 그리고 다른 각종 제어비트들이 있다 사용자 프로그램은 PSW의 전체를읽을 수 있으나 몇몇 필드에만 쓰기를 할 수 있다. 시스템 호출이나 I/O에 중요한 역할을 한다

커널

• 트랩 :사용자 모드에서 커널 모드로 변환을 일으키며 운영체제를 시작하는 명령어, 일이 완료되면 제어권은 사용자 프로그램으로 돌아오며, 시스템 호출을 요청한 명령 바로 다음 명령이 수행된다.
• 트랩 명령의 종류
1. 시스템 호출 : 운영체제로부터 서비스를 받으려면 사용자 프로그램은 커널로 트랩을 걸어서 운영체제를 활용하도록 하는 시스템 호출을 요청해야 한다. I/O나 메모리 보호와 관련된 명령은 사용자 모드에서 허용되지 않기 때문에 시스템 호출을 통해 운영체제에 요청한다.
2. 다른 트랩 명령들 : 대부분은 0으로 나누기나 부동소수점 연산의 언더플로우 현상과 같은 특별한 상황을 알리기 위해 하드웨어에서 일으키는 것들이다. 이 모든 경우에 운영체제가 제어권을 획득하고 트랩의 원인에 따라 어떤 일을 해야 할지를 결정하게 된다.어떤 때는 오류와 함께 프로그램을 강제로 종료할 경우도 있다. 어떤 때에는 오류를 그냥 무시하는 경우도 있다.