로그와 시간복잡도??

시작은 루아스크립트였다..루아스크립트의 구현이 간단하고, 시간복잡도가 O(log n)이기 때문에 레디스에 부담이 없다. 라는 말을 보고 시간복잡도가 뭐지? 하는 궁금증이 생겼다.

📌시간 복잡도??

• 시간복잡도:
  데이터의 양(n)이 늘어날 때, 알고리즘 수행 시간이 얼마나 늘어나는지를 수학적으로 나타낸 것

• 보통 O(1), O(log n), O(n), O(n log n), O(n²) 등으로 표현됨

📌로그가 시간복잡도가 무슨상관이지?

• 로그는 진수가 아무리 크게 증가하더라도, 밑이 존재하기 때문에 지수는 느리게 증가한다.
  그래서 시간복잡도 관점에서 유리하다.

📌로그와 이진트리?

• 이진트리는 각 노드가 최대 2개의 자식 노드를 가진다.
  따라서, 구조적으로 밑이 2인 로그와 같다.
  왜냐면, 로그는 "밑을 몇 번 곱해야 진수가 되는가"를 묻는 함수니까.
  일반적인 로그에서는 지수가 시간복잡도의 핵심인 n,
  이진트리에서는 진수가 n이다.

• 트리 탐색(삽입/삭제/검색)도 O(log n)만큼 걸리기 때문에 빠르다.

📌그럼 인덱스와 시간복잡도도 관련이 있을까?

• Java에서 @Id나 @Index 어노테이션으로 인덱스를 걸 경우 B+Tree/B-Tree 인덱스가 생성된다.
  B+Tree/B-Tree에 대해선 추후 공부할 예정, 이 구조도 결국 Olog(n)으로 시간복잡도가 낮다.
  따라서 인덱스는 테이블이 깊고 복잡해도 조회가 빠르다.

📌B+Tree/B-Tree도 트리 탐색을 하는데 왜 인덱스는 삽입/삭제가 느릴까?

1. 변형에 필요한 추가작업

   • 인덱스의 탐색은 O(log n)으로 빠르게 끝남
   • 인덱스의 삽입/삭제/수정은 추가 작업이 필요하여 시간 복잡도 증가
     • 노드 병합(merge):
       삭제 후 노드가 너무 비게 되면 옆 노드와 병합
     • 재배치(rebalance):
       트리의 균형을 유지하기 위해 상위 노드까지 영향을 줄 수 있음
     • 노드 분할(split):
       하나의 노드에 더 이상 저장할 공간이 없을 경우, 노드를 둘로 나눔
       

2. 디스크 I/O

   • B-Tree는 디스크 기반 구조를 전제로 설계되었기 때문에, 삽입/삭제 과정에서 디스크에 쓰기 작업이 발생.
     읽기보다 쓰기 I/O가 느리기 때문에 이 또한 시간 증가 요인이 됨

3. 정렬

   • 인덱스는 항상 정렬된 상태를 유지해야 함
     그래서 새로 데이터를 넣거나 지울 때도 정렬 조건을 만족시키려는 작업이 필요
     이것이 시간 복도를 높이는 요인이 됨

4. 결론

   삽입/삭제/수정도 이론상 O(log n)이지만,
   구조 재조정 + 디스크 I/O + 정렬 유지 작업 때문에 상대적으로 느리게 느껴짐