julia coding story

□ B+ tree개념 : 실세계에서 가장 널리 활용되는 B-tree : 인덱스 구조와 시퀀스셋(데이터셋)으로 구성 : 인덱스 구조의 루트를 제외한 모든 노드들은 at least half full(절반 이상) 조건을 만족함 (단, 초기 상황은 예외) ▶ 인덱스 구조 ○ 각 노드가 레코드 대신 (오른쪽으로 갈지, 왼쪽으로 갈지만 알려주는) key 값 만으로 구성된 B-tree ○ 노드의 key 값은 데이터 노드로 찾아가는데 이요하는 navigation에 이용 - 노드의 key 값보다 작거나 같으면 search_key node_key 그 노드의 다음 key 값과 비교 - 만약 다음 key 값이 없으면 그 노드의 맨 우측 포인터로 이동 ○ B-tree의 requirements(필요조건)와 constraints(..

□ B-Tree의 Deletion의 법칙 1. underflow 안일어날때 : 그냥 하나씩 삭제해서 밀어넣어주면 됨 2. underflow 일어날때 1) " underflow가 일어난 노드의 형제 노드의 수 > 최소한 가져야 하는 레코드 수" 라면 Redistribution Redistribution : 부모에서 underflow 노드 채우고 다른 형제 노드에서 나간 자리에 채우기 2) "underflow가 일어난 형제 노드의 수 < 최소한 가져야 하는 레코드 수 " 라면 Merge Merge : 부모가 내려오면서 부모에 딸린 노드들을 다 합침 □ B-Tree의 Deletion 구현 (파이썬) int B_tree_deletion(char* out_key) { nodeptr curr, r_sibling, ..

□ B-Tree Insertion - in_rec : insertion 될 레코드, in_key : insertion될 레코드의 key값, pointer P : in_rec노드의 주소(초기값 null) - 밑의 코드에 주석 처리함 // 레코드 하나를 삽입하는 함수이다. // 반환값: 0: 삽입실패, 1, 2: 삽입성공 (1: 층증가 없이, 2:한 층 더 늘어 남.) int insert_arec(ele in_rec) {//하나의 레코드를 삽입 key = 회사명 int i, j; nodeptr curr, child, new_ptr, tptr = NULL; ele empty = { "\0",0 }; big_node bnode; if (!root) {// root가 NULL이면 btree가 비어있음. 맨 첫 노..

□ Retrieval 구현 C언어 - l_sibling : 왼쪽 노드, r_sibling : 오른쪽 노드 - 아래의 코드를 설명해준다. // 좌측형제노드 내용, 부모의 레코드, 우측형제 내용을 받아서 재분배를 하는 함수 // wcase: curr 가 좌측형제와 재분배이면 ‘L’, curr 가 우측형제와 재분배이면 ‘R’. // j : father 안에서 curr를 가리키는 포인터의 인덱스임. void redistribution(nodeptr father, nodeptr l_sibling, nodeptr r_sibling, char wcase, int j) { int i, k, m, n, h; two_Bnode twoB; // twobnode(bnode의 2배의 공간) if (wcase == 'L') j ..

□ B-Tree의 필요성 탐색에 효율적인 Binary Search Tree(BST)가 있음 BST의 문제점 : BST의 insertion 알고리즘은 balanced상태를 보장하지 못한다. (한 쪽 방향으로 편향될 수 있음) -> 탐색 시간이 길어짐 Balance 상태를 유지하는 AVL Tree의 문제점 균형 유지로 인해 일정 수준의 검색 성능을 보장하는 대신, 자료의 개수가 증가하여 트리의 높이가 계속해서 높아짐 (찾아가는 시간이 증가) 삽입/삭제가 빈번하게 발생하면 균형 유지에 소모되는 시간이 많아짐 디스크의 접근 단위는 블록(컴퓨터) 한 바이트만 읽거나 쓰고 싶어도 한 블록을 통째로 읽어오거나 써야함 이 블록을 소프트웨어 레벨에서는 보통 페이지라고 라고 함 검색 트리가 방대하다면, 검색 트리를 메모리..

1. HashMap이란? Map은 키(key)와 값(value)으로 구성된 Entry객체를 저장하는 구조를 가지고 있는 자료구조이다. 여기서 키(key)와 값(value)은 모두 객체이다. 특징 - 값(value)은 중복 저장될 수 있지만 키(key)는 중복 저장될 수 없다. - 만약 기존에 저장된 키(key)와 동일한 키(key)로 값을 저장하면 기본의 값이 삭제되고 새로운 값으로 대 체된다. - 많은 양의 데이터를 검색하는 데 있어서 뛰어난 성능을 보인다. - HashMap은 내부에 'key'와 'value'을 저장하는 자료구조를 가지고 있다. - 해시 함수를 통해 'key'와 'value'이 저장되는 위치를 결정하여 사용자는 그 위치를 알 수 없고 삽입되 는 순서와 들어있는 위치 또한 관계가 없다...

문제는 이해하기 쉬워요. 입력과 출력 예시를 보면 중복체크를 해야해하니 Hashset 를 이용해볼게요. 1. 메모리 1332ms pritnln을 사용해서 각자 계속 출력시키면 1332ms가 나온다. 근데 여기서 그냥 append 를 사용해 거기에 넣어서 한번에 출력시키면 메모리가 줄더라고요. 그게 2번입니다. import java.util.Set; import java.util.ArrayList; import java.util.HashSet; import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.StringTokenizer; public class Main { p..

1. BufferedReader (vs Scanner) - 버퍼를 이용해서 읽는 함수 - 입출력이 효율적으로 좋아짐(vs Scanner에 비해 상대적으로 빠름) ( 하드디스크는 원래 속도가 엄청 느리고 키보드나 모니터와 같은 외부장치와 데이터 입출력은 생각보다 시간이 걸리는 작입이다. 버퍼링 없이 키보드가 눌릴때마다 눌린 문자의 정보를 목적지로 바로 이동시키는 것보다 중간에 메모리 버퍼를 둬서 데이터를 한데 묶어서 이동시키는 것이 보다 효율적이고 빠르다.) - 엔터만 경계로 인식하고 받은 데이터가 String으로 고정된다. (vs Scanner: 띄어쓰기, 엔터를 경계로 값 인식) - integer.parseInt() 형변환을 통해 사용 BufferedReader 사용방법 import java.io.Bu..