해시 테이블이란? 여러가지 물건들이 있는데, 이걸 일렬로 세워놓지 말고 바구니 몇개 만들어서 바구니 A, 바구니 B, …에 넣어두자는거다. key, value 쌍으로 자료를 저장하는 자료구조중 하나. key → 해시값 → index 해시 함수를 사용하여 key를 해시값으로 매핑하고, 이 해시값을 index 혹은 주소 삼아 데이터의 값(value)을 키와 함께 저장하고 검색하는 자료구조. 해시 함수(hash function)란, 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수. 이 때 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시값(hash value), 매핑하는 과정 자체를 해싱(hashing)이라고 한다. 시간 복잡도 O(1) ~ O..
트랜잭션(transaction)이란? 한 묶음으로 처리되도록 만든 SQL 명령문들을 묶은 작업 단위 대부분의 의미 있는 서비스 처리를 하려면 SQL 명령문 한번 (SELECT, UPDATE, …)만으로는 어렵다. 계좌이체라는 작업을 예시로 들어보자. 만약 X의 돈을 100 감소시키는 UPDATE 문 직후에 서버가 다운되면 어떻게 될까? 더 이상 서버에선 쿼리문을 날리지 못하니, Y에겐 100만큼의 돈이 가지 않고 회사가 X의 돈을 훔친 꼴이 된다(!). 그리고 갑작스러운 서버 다운, 네트워크 오류, 데이터센터 화재 등 데이터베이스의 일관성을 위협하는 요소들은 생각보다 많다. 이를 해결하기 위해선 계좌이체라는 하나의 처리를 { X 잔고 UPDATE 문, Y 잔고 UPDATE 문 } 한 단위로 묶어서 모두 ..
B-tree란? 이진트리를 확장한 자료구조로, 탐색 성능을 높이기 위해 평소에 데이터들의 높이를 균형있게 유지하는 Balanced Tree의 일종이다. 노드에는 2개 이상의 데이터(key)가 들어갈 수 있다. 하나의 노드가 가질 수 있는 자식의 최대 숫자가 2보다 크다. 모든 단말(leaf) 노드는 같은 레벨에 있어야 한다. 항상 균형을 유지한다 (균형 잡힌 트리). 최대 M개의 자식을 가질 수 있는 B 트리를 M차(M-way) B트리라고 한다. 내부 노드는 M/2 ~ M개의 자식을 가질 수 있다. (e.g. 3차 B트리 : 1~3개의 자식 노드 가능) 노드 내에 **데이터(key)**는 floor(M/2)-1개부터 최대 M-1개까지 포함될 수 있다 특정 노드의 데이터(key)가 K개라면, 자식 노드의 ..
인덱스란? : 테이블 안의 데이터를 쉽고 빠르게 찾을 수 있도록 만든 데이터베이스 객체. 책의 목차나 색인을 통해 더 빠르게 내용을 찾는것과 같은 개념이다. 특정 속성에 인덱스를 생성하면, 해당 속성에 대한 데이터들을 정렬해서 별도의 메모리 공간에 데이터의 물리적 주소값(디스크 블록의 주소값)과 함께 저장된다. DB와 디스크DB 데이터가 물리적으로 저장되는 곳은 디스크(보조기억장치)이기 때문에, SQL 실행시 디스크로부터 필요한 데이터를 찾게 된다. DBMS는 필요한 디스크 블럭을 반복해서 주기억장치로 읽어오게 되는데, 문제는 디스크 접근 속도가 주기억장치보다 비교할 수 없을 정도로 너무 느리다는 점이다.DB의 테이블 데이터들은 모두 블록 단위로 관리된다. 만약 쿼리를 통해 1개의 레코드를 읽고 싶더라도..
컴공 복수전공 시작 2021년은 휴학을 하면서 내 진로를 찾았던 중요한 해다. 친구의 권유로 프론트엔드 (html, css, JS)를 배워봤고, 웹 앱 개발에 관심을 갖게 되면서 부트캠프 백엔드 과정을 등록, 수료했다. 부트캠프는 효율성 측면에서 그닥 좋지 않았지만, 개발에 뜻을 가진 사람들(다른 분야에 종사하시다 개발에 관심을 갖게된 분들과 커뮤니케이션해보는 경험이 새로웠다.) 2021년은 방황을 멈추고 진로를 정했기 때문에 굉장히 뜻깊은 해였다. 그렇게 2022년도 컴퓨터학과 복수전공을 신청했다. 1학기에 배우게 된 미적분과 확률통계는 생각보다 재미있었다. 교수님의 강의보다는 책에 담겨있는 내용이 재밌었다. 편입 수학을 공부하면서 수학적인 사고방식에 재미를 붙였던게 도움이 됐다. 이 사고방식은 당장 ..
관계형 데이터 모델 관계형 데이터 모델은 릴레이션(relation)이라는 수학적 개념에 기초하고 있다. 결국 릴레이션(relation)은 동일한 구조로 이뤄진 튜플(tuple)의 집합이고, 2차원 테이블(table) 형태의 단순한 구조다. (테이블 개념은 내부 저장 구조에 대한 추상적인 표현일 뿐이고, 물리적으로는 복잡한 구조 속에 데이터가 저장된다.) 관계형 데이터베이스는 데이터 묶음을 릴레이션(테이블)의 형태로 저장한다. 주로 테이블이라고 불린다. 💡 릴레이션(테이블) Student라는 릴레이션을 상상해보자. 학번이름학과나이전화번호MBTI 170 원석 컴퓨터SW 27 010123123 INTP 180 영두 컴퓨터SW 24 010456456 ISTP 181 성욱 정보보호 24 010789789 INFP..
데이터베이스 시스템(DBMS)을 쓰는 이유 파일 정보 시스템의 문제점: 데이터 중복성, 비일관성 검색의 비효율성 데이터들간에 연결성 부족(여러 파일에 같은 종류의 데이터가 흩어져있을 수 있음) 동시 접근 불가능 및 데이터 무결성 부족(여러 사용자가 접근할 때 데이터에 손상이 생길 수 있다) 복구 어려움 데이터베이스 관리 시스템(DBMS)의 장점: 데이터의 독립성 물리적 독립성 : 데이터베이스 사이즈를 늘리거나 성능 향상을 위해 데이터 파일을 추가하더라도 관련된 응용 프로그램을 수정할 필요가 없다. 논리적 독립성 : 데이터베이스는 논리적인 구조로 다양한 응용 프로그램의 논리적 요구를 만족시켜줄 수 있다. 데이터 종속성 최소화 데이터 저장 방식과 접근 방식에 변화가 생기더라도 관련된 응용 프로그램 수정의 부..
선형 자료구조 Therefore, we can traverse all the elements in single run only. Linear data structures are easy to implement because computer memory is arranged in a linear way. 스택, 큐, 데크는 모두 추상 자료형(ADT)이다. 즉, 언어에서 기본적으로 제공되는게 아니라 데이터와 연산들에 의해 정의되는 추상적인 자료구조이다. 각각을 구현하는건 프로그래머의 몫이다. 스택, 큐, 데크 모두 선형 자료 구조이며 각자 특정 방향으로 **삽입(push), 삭제(pop)**가 된다는 특징을 갖고 있다. 그리고 n개의 원소들로 이뤄진 선형 리스트이다. 그렇기 때문에 보통 is_empty() ..
