CS2026.09.146 min read

Directory: 파일명과 inode를 연결하는 계층적 네임스페이스

디렉터리는 파일명과 inode 번호를 매핑하는 특수한 파일로, 파일시스템에 계층 구조와 이름 공간을 제공한다. 내부 구현 방식(선형 리스트, 해시, B-tree)에 따라 탐색 성능이 크게 달라지며, ext4의 htree나 NTFS의 B+tree처럼 실제 파일시스템은 대용량 디렉터리 성능 문제를 해결하기 위해 트리 기반 색인을 사용한다. 이 글에서는 디렉터리

By 송민성

1. 개념

디렉터리(Directory)는 파일 이름과 해당 파일의 메타데이터 위치(inode 번호)를 연결해주는 특수한 형태의 파일이다. 사용자 입장에서는 "폴더"처럼 보이지만, 운영체제 내부에서는 (파일명, inode 번호) 쌍의 목록을 저장하는 자료구조에 불과하다.

디렉터리 자체도 파일이기 때문에 자신만의 inode를 가진다. 디렉터리의 inode는 "이 디렉터리는 디렉터리 타입이다"라는 정보와 함께, 실제 엔트리 목록이 저장된 데이터 블록을 가리킨다.

text

디렉터리 /home/user/ 의 내용 예시

파일명        inode 번호
----------   ----------
.               1523
..              1024
report.txt      2048
photos/         2051

여기서 .은 자기 자신, ..은 부모 디렉터리를 가리키는 특수 엔트리다. 이 두 엔트리 덕분에 상대 경로 탐색과 트리 순회가 가능해진다.

2. 왜 사용하는가

파일시스템이 디렉터리라는 계층 구조를 제공하지 않는다면, 디스크에 저장된 모든 파일은 inode 번호로만 구분되는 평평한(flat) 집합이 된다. 이 경우 사람이 파일을 찾으려면 전체 inode 목록을 순회하며 원하는 파일을 찾아야 한다.

디렉터리는 다음 문제를 해결한다.

이름 공간 분리: 서로 다른 디렉터리에 같은 이름의 파일이 존재할 수 있다.
계층적 조직화: /var/log/nginx/access.log처럼 논리적 그룹핑이 가능하다.
접근 제어의 단위: 디렉터리 단위로 권한(rwx)을 설정해 하위 파일 접근을 제어할 수 있다.
빠른 탐색을 위한 색인 구조의 기반: 트리 형태이므로 경로 탐색 시 각 단계에서 탐색 범위를 좁힐 수 있다.

3. 동작 원리

경로 탐색(Path Resolution)

/home/user/report.txt를 여는 과정은 다음과 같다.

루트 디렉터리(/)의 inode(보통 inode 번호 2)를 커널이 알고 있다.
루트 디렉터리의 엔트리 목록에서 home을 선형 탐색 또는 색인 탐색으로 찾아 inode 번호를 얻는다.
해당 inode가 가리키는 데이터 블록(즉 home 디렉터리의 엔트리 목록)에서 user를 찾는다.
같은 방식으로 report.txt의 inode 번호를 찾는다.
최종 inode에서 실제 파일 데이터 블록 위치를 얻는다.

경로의 깊이만큼 이 과정이 반복되므로, 디렉터리 하나당 탐색 비용이 전체 파일 열기 비용에 직접 영향을 준다.

디렉터리 내부 구현 방식

선형 리스트(Linear List): 초기 Unix 파일시스템과 ext2가 기본으로 사용한 방식이다. (파일명, inode 번호) 쌍을 배열이나 연결 리스트로 순서대로 저장한다. 구현이 단순하지만 엔트리가 많아지면 탐색 비용이 선형으로 증가한다.

해시 테이블(Hash Table): 파일명을 해시하여 버킷에 저장한다. 평균적으로 빠른 탐색이 가능하지만 해시 충돌이 많아지면 성능이 저하되고, 정렬된 순서로 디렉터리를 나열하기 어렵다.

B-tree / B+tree 기반 색인: NTFS, XFS, ReiserFS가 사용하는 방식이다. 파일명(또는 해시값)을 키로 하는 균형 트리를 구성해 탐색, 삽입, 삭제를 모두 로그 시간에 처리한다. ext4는 htree라는 해시 기반 B-tree 변형 구조를 사용해 대용량 디렉터리를 지원한다.

4. 코드 예제

디렉터리 엔트리를 해시 테이블로 흉내 낸 간단한 시뮬레이션과, 실제 파일시스템 디렉터리를 순회하는 코드를 함께 본다.

python

# 디렉터리를 해시 테이블 기반으로 흉내 낸 간단한 시뮬레이션
# 실제 ext4 htree, NTFS B+tree의 개념을 단순화한 모델

class DirectoryEntry:
    def __init__(self, name: str, inode_number: int):
        self.name = name
        self.inode_number = inode_number


class HashDirectory:
    """해시 테이블 기반 디렉터리 구현. 평균 O(1) 탐색을 목표로 한다."""

    def __init__(self, bucket_count: int = 16):
        self.buckets: list[list[DirectoryEntry]] = [[] for _ in range(bucket_count)]
        self.bucket_count = bucket_count

    def _hash(self, name: str) -> int:
        return hash(name) % self.bucket_count

    def add_entry(self, name: str, inode_number: int) -> None:
        bucket = self.buckets[self._hash(name)]
        for entry in bucket:
            if entry.name == name:
                raise FileExistsError(f"'{name}' 이미 존재함")
        bucket.append(DirectoryEntry(name, inode_number))

    def lookup(self, name: str) -> int | None:
        bucket = self.buckets[self._hash(name)]
        for entry in bucket:
            if entry.name == name:
                return entry.inode_number
        return None

    def remove_entry(self, name: str) -> bool:
        bucket = self.buckets[self._hash(name)]
        for i, entry in enumerate(bucket):
            if entry.name == name:
                del bucket[i]
                return True
        return False


# 사용 예
directory = HashDirectory()
directory.add_entry("report.txt", 2048)
directory.add_entry("photos", 2051)

print(directory.lookup("report.txt"))  # 2048
print(directory.lookup("missing.txt"))  # None

python

# 실제 파일시스템 디렉터리를 재귀적으로 순회하는 예제
# os.walk는 내부적으로 각 디렉터리에서 getdents 계열 시스템 콜을 호출한다

import os

def walk_and_print(root_path: str, max_depth: int = 2) -> None:
    root_depth = root_path.rstrip(os.sep).count(os.sep)
    for current_dir, sub_dirs, files in os.walk(root_path):
        depth = current_dir.count(os.sep) - root_depth
        if depth > max_depth:
            sub_dirs[:] = []  # 더 깊은 탐색을 막는다
            continue
        indent = "  " * depth
        print(f"{indent}{os.path.basename(current_dir)}/")
        for f in files:
            print(f"{indent}  {f}")


if __name__ == "__main__":
    walk_and_print(".", max_depth=1)

5. 시간 복잡도 또는 성능 특성

구현 방식	탐색	삽입	삭제	사용 예
선형 리스트	O(n)	O(n) (중복 검사 포함)	O(n)	ext2, 초기 Unix FS
해시 테이블	평균 O(1), 최악 O(n)	평균 O(1)	평균 O(1)	일부 FS의 캐시 계층
B-tree / B+tree	O(log n)	O(log n)	O(log n)	NTFS, XFS, ReiserFS
htree (해시+트리 혼합)	O(log n) 근사	O(log n) 근사	O(log n) 근사	ext3(옵션), ext4(기본)

n은 디렉터리 내 엔트리 개수다. 경로 전체를 탐색하는 비용은 경로 깊이 d에 대해 각 단계 탐색 비용을 곱한 값에 근접하므로, 디렉터리 깊이가 깊고 각 디렉터리의 엔트리 수가 많을수록 파일 열기 비용이 커진다.

6. 실무 사용 사례

ext4의 htree: 디렉터리 엔트리가 일정 개수를 넘으면 ext2 방식의 선형 리스트 대신 파일명의 해시값을 키로 하는 트리 구조로 전환한다. 수만 개 이상의 파일이 있는 디렉터리에서도 탐색 성능 저하를 줄인다.

NTFS의 B+tree: 디렉터리 인덱스를 B+tree로 관리해 파일명 정렬 조회(dir 명령의 이름순 정렬 출력)와 탐색을 모두 로그 시간에 처리한다.

리눅스 dentry cache (dcache): VFS 계층에서 최근 조회한 경로명과 inode 매핑을 캐시에 보관해, 디스크 I/O 없이 경로 탐색을 가속한다. ls, find 같은 명령어의 반복 실행이 빨라지는 이유다.

shell

# 디렉터리 엔트리 수가 많은 경우 확인
ls -la /var/spool/postfix/maildrop | wc -l

# 디렉터리 자체의 크기(엔트리 목록 저장 공간)와 파일 크기는 다르다
stat /home/user

7. 주의할 점

대용량 디렉터리의 선형 탐색 문제: 선형 리스트 방식의 디렉터리에 수십만 개의 파일을 넣으면 ls, open() 같은 단순 조회 연산도 눈에 띄게 느려진다. 로그 파일이나 세션 파일을 한 디렉터리에 무한정 쌓는 설계는 피해야 한다.

심볼릭 링크로 인한 순환 참조: 디렉터리 트리를 재귀적으로 순회하는 코드에서 심볼릭 링크가 상위 디렉터리를 다시 가리키면 무한 루프에 빠질 수 있다. os.walk는 기본적으로 심볼릭 링크를 따라가지 않지만(followlinks=False), 옵션을 켰다면 방문한 inode를 기록해 중복 방문을 막아야 한다.

`.`과 `..`의 특수성: 디렉터리 엔트리 목록을 순회할 때 .과 ..을 실제 하위 항목으로 착각해 잘못된 재귀 삭제나 순회를 하지 않도록 걸러야 한다.

디렉터리도 크기 제한이 있다: 파일시스템에 따라 디렉터리 하나가 가질 수 있는 엔트리 수나 디렉터리 자체의 최대 크기에 제한이 있을 수 있다. 대량 파일 생성 배치 작업에서는 해시 기반 서브디렉터리 분산(예: 파일명 해시 앞 두 글자로 서브디렉터리 분리)이 흔히 쓰이는 우회 전략이다.

8. 핵심 정리

디렉터리는 파일명과 inode를 연결하는 특수 파일이며, 내부 구현 방식(선형 리스트, 해시 테이블, B-tree)에 따라 탐색 성능이 O(n)에서 O(log n)까지 달라진다. 실무에서 대용량 디렉터리를 다룰 때는 파일시스템이 어떤 색인 구조를 쓰는지 이해하고, 필요하다면 서브디렉터리 분산 같은 애플리케이션 레벨의 대응 전략을 함께 고려해야 한다.