생각을 개발하자, 박진형

[TIL - 0904] ArrayList vs LinkedList, 인덱스 내부 동작 알아보기

Java API

ArrayList vs LinkedList

  • 많이 쓰는 자료구조지만, 개념적으로 차이도 이해하고 있지만 익숙하다고해서 ArrayList만 사용하지않나?
    • 제대로 사용하기위해서 코드를 눈으로 봐야겠다싶었음

개념적 차이

  • ArrayList는 배열로, LinkedList는 객체 간 연결을 통해 리스트를 만듦
  • ArrayList는 탐색에 유리 : 인덱스
  • LinkedList는 제일 앞, 뒤 확장에 유리 : 삽입이 빈번할 때 유리

API 코드 확인

  • LinkedList
/* head와 tail을 알고 있음 */
transient Node<E> first;
transient Node<E> last;


/* 꼬리에 붙임 */
public boolean add(E e) {
    linkLast(e);
    return true;
}


/* 중간 삽입 - 위치 확인 후 중간인 경우 앞 뒤의 연결을 끊고 다시 맺기만 하면 됨 */
public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}


/* 탐색 - node() 메소드를 따라가보면 index 까지 처음부터 혹은 마지막부터 순차탐색해서 찾음, 최악의 경우 중간에 위치한 경우 거기까지 가야함 */
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
  • ArrayList
/* 배열 초기화 */
public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
        }
    }
    
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; // 빈 배열, 처음 add가 일어날 때 크기를 늘림
}


/* 크기부터 체크 - 확장 후 데이터 삽입 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}


/* 중간부분 삽입할 경우 사이즈 체크 + 배열의 원소 카피 작업까지  */
public void add(int index, E element) {
    rangeCheckForAdd(index); // IndexOutBoundException 체크

    ensureCapacityInternal(size + 1);
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}


/* 탐색 - 바로 찾음 */
public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}

같은 리스트라도

  • 내부 구현은 다름 : 각각의 자료구조 특성에 대해서 이해를 하고 있어야 제대로 사용할 수 있지 않을까…..
    • 매번 ArrayList만 사용하던 나도 반성을….자료구조가 어떻게 쓰이는지에 따라 생각하고 사용하기

인덱스

  • 사용을 직접해서 속도가 확 줄어드는 것은 보았는데, 어떻게 내부적으로 동작하는지 모르니 여러 자료를 통해서 알아봄
  • 디스크 IO 횟수를 줄여줌

인덱스 종류

  • 클러스터 인덱스 : 범위의 첫 데이터와 페이지의 주소가 맵핑된 B-Tree 생성(주제와 쪽수가 맵핑된 책 인덱스), 테이블 당 1개(PK)
    • 따로 정렬해주지않았지만 인덱스 생성 시 오름차순으로 정렬됨 : 오래 걸림 - 정렬을 하기때문에
mysql> insert into user values ('LSG', '이승기', 1987), ('KBS', '김범수', 1979), ('KKH', '김경호', 1971), ('JYP', '박진영', 1976), ('SSK', '성시경', 1979), ('LJB', '임재범', 1963);
mysql> select * from user;
+--------+-----------+-----------+
| userId | name      | birthYear |
+--------+-----------+-----------+
| JYP    | 박진영     |       1976 |
| KBS    | 김범수     |       1979 |
| KKH    | 김경호     |       1971 |
| LJB    | 임재범     |       1963 |
| LSG    | 이승기     |       1987 |
| SSK    | 성시경     |       1979 |
+--------+-----------+-----------+
  • 보조 인덱스(secondary) : 컬럼의 데이터를 가지고 인덱스 페이지를 만듦(원래 데이터의 정렬에는 아무런 영향을 미치지않음), 테이블 당 여러개를 생성할 수는 있음
    • key로는 컬럼의 데이터, value로는 해당 데이터 위치(페이지주소 + row)
    • 인덱스도 페이지고, 페이지의 저장 한계를 넘어가면 분할을 하고, secondary index는 특정 컬럼의 데이터를 뽑고 데이터의 위치를 저장함 : 데이터가 많을 시에는 분할된다는 점!
    • 해당 컬럼이 많이 검색된다면 고려해봐야..!
+--------+-----------+
| key    | value     |
+--------+-----------+
| LSG    | 1000+#2   |
| KBS    | 1001+#4   |
| KKH    | 1001+#2   |
| JYP    | 1001+#1   |
| SSK    | 1003+#2   |
| LJB    | 1000+#1   |
+--------+-----------+
  • 두 인덱스가 혼합되어있는 경우 + secondary index 컬럼으로 검색하는 경우 : secondary index에는 데이터(key), clustered index의 key가 value로 저장됨(데이터 위치를 바로 저장하지않음)
    • 데이터 입력되었을 때 secondary index의 value가 계속 바뀌니깐 성능을 위해서 value로 clustered index의 key를 저장
    • 결론 : secondary index -> clustered index 거치게 됨 : 결국 clustered index의 key로 clustered index에서 찾게 되는 것

인덱스 내부 동작

페이지가 뭐지?

  • 페이지 : 데이터 저장 블록, 인덱스도 똑같음 - 데이터를 저장하는데 단순 데이터가 아니라 범위 검색을 위한 데이터를 저장하고있음
    • 페이지에는 용량 제한이 걸려있음 : MySQL의 경우 16KB, 한 페이지에 꽉찰 경우 페이지 분할을 하게됨

인덱스 생성하면?

  • 인덱스를 생성하면 원래 데이터 저장 블록이 B-Tree의 리프 노드, 데이터 범위의 첫시작 데이터로 이뤄진 B-Tree 루트노드로 구성됨
    • 루트 노드도 페이지 : 꽉차면 페이지 분할하고 브랜치 노드로 되고 최상위(루트) 노드가 하나 새로 생김 - Insert 작업에서 느릴 수 있다는 이유였음
  • 원래라면 데이터들이 저장된 블록만 있었으니깐 데이터를 찾으려면 풀스캔을 해야했지만 인덱스 페이지가 있으니 인덱스에서 범위를 보고 해당 데이터 저장 블록으로 가게됨 : 빠르게 찾을 수 있게된 것
  • Clusterd Index와 Secondary Index 생성 차이 : Clusterd Index는 생성하면 데이터 정렬 자체가 변경되지만, Secondary Index는 실제 데이터에는 영향은 없으나 컬럼 데이터를 가지고 다시 새로운 인덱스 페이지를 만듦

이 컬럼 인덱스 만들어야할까? 말아야할까?

  • 남/녀로 구분되는 데이터를 인덱스로 만들고, 남자인 데이터를 검색한다면? 굳이 인덱스 페이지(secondary -> clustered)를 거쳐서 데이터 페이지로 올 필요가 없음
  • 다양한 값이 많이 포진될수록 인덱스 효과가 발휘됨 : 조금 더 자세히 알아보기

참고자료