Medium에 기재된 ‘Advanced Data Structures for Data Engineering — Part I’ 글을 토대로 정리한 데이터 엔지니어가 꼭 알아야 하는 자료구조

1. DAG(Directed Acyclic Graph)

   

   DAG란, 노드와 노드 사이를 잇는 간선에 **방향(Directed)**이 있고, 시작노드(Z1)에서 시작해서 마지막에는 다시 시작노드(Z1)로 돌아오는 순환 반복 실행이 될 수 있는 방법이 없는 비순환(Acyclic) 특징을 가지는 그래프 자료구조 중 하나의 종류를 말한다.

   일반적으로 DAG는 작업들의 우선순위를 표현 할 때 DAG를 많이 사용한다. 예를 들어, 데이터 엔지니어들이 가장 많이 개발하는 ETL을 생각해보자. Extract → Transfer → Load 라는 순서와 실행 조건(이전 작업의 정상 완료)이 무조건 지켜야 한다. 그렇지 않다면 정상적으로 데이터가 적재되지 않을 것이다. 이렇게 작업 간의 순서를 그래프로 표현할 때는 DAG로 표현하는게 일반적이다.

   • DAG가 적용된 프로그램 Example) Airflow

2. Skip List

   Linked List와 유사한 자료구조 중 하나. Linked List의 자료구조의 경우, insert/delete는 속도가 굉장히 빠르다라는 장점이 있지만, 단점으로는 search의 속도가 느린다라는 단점이 있다.(검색 속도가 느린 이유는 처음 노드부터 마지막 노드까지 순차적으로 접근할 수 밖에 없기 때문에 | 시간 복잡도 O(n))

   이러한 단점(?)을 극복하는 자료구조가 Skip List이다. 기존 Linked List에서는 다음 노드(now_node + 1)의 메모리 주소 값이 저장되어 있는 포인터 address와 값을 저장하고 있는 value가 있었다면 Skip List는 하나의 메모리 address(now_node + 2, now_node + 3)를 더 가지고 있다. 그래서 검색 속도를 n/2로 줄이는 자료구조 형태이다.

   Search — avg O(logn) worst O(n)

   Insertion — avg O(logn) worst O(n)

   Deletion — avg O(logn) worst O(n)

   Skip List는 AVL trees 또는 splay trees 자료구조를 대체할 수 있고, Redis가 메모리 데이터를 저장할 때 데이터 구조로 사용되고 있다.

3. LSM Tree

4. Hash Index

5. B-Tree

6. Inverted Index

7. R-Tree