Back to Index | frex.github.io. Generated from representing-file-tree.md using makearticle.py on 2026-08-10 02:48.

Representing file tree

The task

The task we want to complete is to iterate over a large file tree (directories that contain files and other) and gather all the filenames into some efficient (whether that means RAM or CPU wise) and (ideally) convenient to use and not too complex or error prone to implement data structure, for later processing.

I will go over a few approaches I used in the past, and show example code in Python for most of them, and note advantages and disadvantages (of both a Python implementation and in general or in context of language like C++).

For clarity I will also try to consistently use terms "f" or "file", "d" or "dir" or "directory", "name" and "path". For example file.txt is a filename, D:\data\file.txt is a file path, data is a dir name, D:\data is a dir path, and so on.

Approach 1: list of filepaths

This is the most obvious and simplest approach, just store in a list (or equivalent/similar, and possibly sorted or dedupped) every full filepath. This approach is probably okay unless there is a lot of very long dirpaths.

Advantages:

  1. simplest to program.
  2. stores ready to use filepaths.

Disadvantages:

  1. every filepath stores a coyp of the entire directory path in its data.
"""Example of storing each filepath in a list."""

import sys
import os


def _main():
    allfiles = []
    for dirpath, _, filenames in os.walk(sys.argv[1]):
        for fname in filenames:
            allfiles.append(os.path.join(dirpath, fname))

    allfiles = list(allfiles)  # remove reserved unused capacity from list

    allfiles_size = sys.getsizeof(allfiles)
    elements_size = sum(map(sys.getsizeof, allfiles))
    total_size = allfiles_size + elements_size

    print(f"{len(allfiles)} aka {len(allfiles) / 1000:7.3f} thousand files")
    print(f"List size         : {allfiles_size / (1024.0 * 1024.0):7.3f} MiB")
    print(f"Elements sum size : {elements_size / (1024.0 * 1024.0):7.3f} MiB")
    print(f"Total size        : {total_size / (1024.0 * 1024.0):7.3f} MiB")


if __name__ == "__main__":
    _main()

132465 aka 132.465 thousand files
List size         :   1.011 MiB
Elements sum size :  24.060 MiB
Total size        :  25.071 MiB

Approach 2: list of dirpath + filename pairs

This is the second most obvious approach, instead of storing each filepath already concatenated, we store a list of pairs of dirpath and filename, and use pointers, references, etc. (details vary by language) to store single copy of dirpath. Another version of this approach could be a mapping/hashtable from dirpath to list of filenames.

Advantages:

  1. still very simple to program in most languages.
  2. the pairs are still easy to pass around various places in your program.
  3. (niche) naturally lends itself to using *at style APIs like openat.
  4. slightly lower memory usage by not storing all the duplicate copies of the dirpath.

Disadvantages:

  1. a bit more tricky to program in some lower level languages.
  2. in some languages (including Python, but not C and C++) there is RAM overhead of storing a pair as a tuple, and CPU/cache overhead of accessing it, since it's a separate object in memory.
  3. requires concatenation (which in some languages necessitates an allocation) to create a filepath to pass to some API.
"""Example of storing pairs of dirpath and filename in a list."""

import sys
import os


def _main():
    allfiles = []
    for dirpath, _, filenames in os.walk(sys.argv[1]):
        for fname in filenames:
            allfiles.append((dirpath, fname))

    allfiles = list(allfiles)  # remove reserved unused capacity from list

    allfiles_size = sys.getsizeof(allfiles)
    elements_size = sum(map(sys.getsizeof, allfiles))

    # consider each unique dirpath once when summing up sizes
    dirpaths_size = sum(map(sys.getsizeof, set(d for d, _ in allfiles)))
    filenames_size = sum(map(sys.getsizeof, (fname for _, fname in allfiles)))
    total_size = allfiles_size + elements_size + dirpaths_size + filenames_size

    print(f"{len(allfiles)} aka {len(allfiles) / 1000:7.3f} thousand files")
    print(f"List size         : {allfiles_size / (1024.0 * 1024.0):7.3f} MiB")
    print(f"Elements sum size : {elements_size / (1024.0 * 1024.0):7.3f} MiB")
    print(f"Dirpaths sum size : {dirpaths_size / (1024.0 * 1024.0):7.3f} MiB")
    print(f"Fnames sum size   : {filenames_size / (1024.0 * 1024.0):7.3f} MiB")
    print(f"Total size        : {total_size / (1024.0 * 1024.0):7.3f} MiB")


if __name__ == "__main__":
    _main()

132465 aka 132.465 thousand files
List size         :   1.011 MiB
Elements sum size :   8.085 MiB
Dirpaths sum size :   0.650 MiB
Fnames sum size   :  10.052 MiB
Total size        :  19.798 MiB

Approach 3: pair of list of dirpaths and of filenames

This is the same approach as above, except it accounts for the shortcoming about pairs being separate objects in some languages. This approach is probably not worth it unless every byte and microsecond counts.

Advantages:

  1. lower memory usage and less indirection when accessing the data.

Disadvantages:

  1. all of the ones above, except for pairs being their own objects.
  2. to pass complete filepath around it needs to be stored in a pair or concatenated or two arguments must be passed instead of one.
  3. some operations become harder, e.g. sorting.
"""Example of storing pair of lists of dirpaths and filenames."""

import sys
import os


def _main():
    alldirpaths = []
    allfilenames = []

    for dirpath, _, filenames in os.walk(sys.argv[1]):
        for fname in filenames:
            alldirpaths.append(dirpath)
            allfilenames.append(fname)

    # remove reserved unused capacity from list
    alldirpaths = list(alldirpaths)
    allfilenames = list(allfilenames)

    alldirpaths_size = sys.getsizeof(alldirpaths)
    allfilenames_size = sys.getsizeof(allfilenames)

    dirpaths_size = sum(map(sys.getsizeof, set(alldirpaths)))  # dedup
    fnames_size = sum(map(sys.getsizeof, allfilenames))

    total_size = alldirpaths_size + allfilenames_size + dirpaths_size + fnames_size

    print(f"{len(alldirpaths)} aka {len(alldirpaths) / 1000:7.3f} thousand files")
    print(f"Dirs list size     : {alldirpaths_size / (1024.0 * 1024.0):7.3f} MiB")
    print(f"Files list size    : {allfilenames_size / (1024.0 * 1024.0):7.3f} MiB")
    print(f"Dirpaths sum size  : {dirpaths_size / (1024.0 * 1024.0):7.3f} MiB")
    print(f"Filenames sum size : {fnames_size / (1024.0 * 1024.0):7.3f} MiB")
    print(f"Total size         : {total_size / (1024.0 * 1024.0):7.3f} MiB")


if __name__ == "__main__":
    _main()

132465 aka 132.465 thousand files
Dirs list size     :   1.011 MiB
Files list size    :   1.011 MiB
Dirpaths sum size  :   0.650 MiB
Filenames sum size :  10.052 MiB
Total size         :  12.724 MiB

Approach 4: a graph like structure with pointers to parent

This approach is a bit similar to how directories and files logically work in the filesystem, but backwards, e.g. starting at the leaf nodes. We store two kinds of structures/tuples/etc.: files that contain filename and a reference/pointer to the dir struct (their parent dir), and dir structs that contain dirname and a reference/pointer to another dir struct - its parent. The root dir can point to itself, or have a nil/null/None for its parent.

Advantages:

  1. most compact (with regard to storing duplicate paths) represenation.

Disadvantages:

  1. trickiest to code, especially in non-GC language.
  2. more concatenation and pointer/ref chasing required to create a full filepath to pass to another API.

Other considerations

Another fun optimizations would be a deeper string dedup in low-level language, including of substrings of each other (the filenames a.txt and data.txt can be stored together, with the former just pointing at 3 bytes further than the latter), e.g. with std::string_view in C++.

No matter how you represent your file tree you can go back to: Index | frex.github.io.