~/systems/in-memory-file-system

In-memory file system

Directories as nested maps, files as leaves. Split the path, walk one name at a time, and do every lookup through one helper.

what

A tree whose directory nodes map child names to nodes (sorted, so listings come out in order) and whose file nodes hold content. Paths are split on "/"; one helper walks existing nodes and another creates missing directories.

use when

Design a file system, cloud storage, a camera card or a path-based config store: mkdir, write, ls, rm, find by extension, sizes per folder.

time

O(depth) per path lookup, O(subtree) for find, du and rm

space

O(total names and content)

You’ll recognise it when

Inputs are paths like /photos/2024/beach.jpg, and the operations are mkdir, ls, write, read, delete.
Missing parent folders must be created on the way, or the call must fail if a file is in the way.
Queries walk a whole subtree: total size of a folder, every .jpg underneath, delete a folder and everything in it.
Listings must come out sorted by name.

It’s often confused with a trie, and it is one: a trie whose edges are whole path components instead of letters. Some variants keep a flat map from full path to file instead, which is simpler until a level asks about folders.

The idea

A filing cabinet has drawers, the drawers hold folders, and folders hold more folders or sheets of paper. To find /photos/2024/beach.jpg you open the drawer called photos, then the folder 2024, then take out the sheet beach.jpg. You never search the whole cabinet.

In code, a directory is a node with children, a map from name to node; a file is a node with content and no children. A path is parts, the list of names you get by splitting on / and dropping empty pieces, so /a//b/ and /a/b are the same path. Every operation is a walk down from the root, one name per step. Put that walk in one helper that returns the node or None, and a second that creates missing directories. Everything else is a few lines on top.

How it works

Split the path. split("/photos/2024/beach.jpg") gives parts = ["photos", "2024", "beach.jpg"]. The root is the empty list.
Find. Start at the root and, for each name, step into children[name]. If the name is missing, or the current node is a file (files have no children), the path doesn’t exist: return None.
Make directories. Same walk, but create a directory for each missing name. If an existing name on the way is a file, stop and return None. Creation only starts after the last existing name, so a failed call changes nothing.
Write a file. Make the directories for all but the last name, then add a file node for the last one, or append to it if it’s already a file. If a directory already has that name, refuse.
List. For a directory, return its child names in sorted order; for a file, return just its own name.
Remove. Find the parent, and delete the last name from its children. A directory goes with everything below it, in one step.
Walk a subtree. For find-by-extension and total size, push the start node on a stack and visit every node below it, building each file’s full path as you go. An explicit stack avoids recursion limits on deep trees.

On a small tree:

call	result
`mkdir /photos/2024`	true
write `/photos/2024/beach.jpg`, `/photos/2024/notes.txt`, `/docs/cv.txt`	true, true, true (creates `/docs`)
`ls /`	`docs photos`
`ls /docs/cv.txt`	`cv.txt`
find `.txt` under `/`	`/docs/cv.txt /photos/2024/notes.txt`
write `/docs/cv.txt/x.txt`	false: `cv.txt` is a file
`rm /photos`, then `ls /`	true, `docs`

Why it’s correct: every node is reached from the root by exactly one path, its list of names. Find and create both follow that path name by name, so they agree on which node a path means, and they never step into a file. Subtree walks visit each node below the start exactly once.

class Node:
    def __init__(self, is_file):
        self.children = None if is_file else {}   # name -> Node, for a directory
        self.content = ""                          # for a file

    @property
    def is_file(self):
        return self.children is None


def split(path):
    return [p for p in path.split("/") if p]       # "/a//b/" -> ["a", "b"]


class FileSystem:
    def __init__(self):
        self.root = Node(is_file=False)

    def _find(self, parts):
        # Walk existing nodes only. None if missing or a file is in the way.
        node = self.root
        for name in parts:
            if node.is_file or name not in node.children:
                return None
            node = node.children[name]
        return node

    def _make_dirs(self, parts):
        # Create missing directories. None (and no change) if a file is in the way.
        node = self.root
        for name in parts:
            child = node.children.get(name)
            if child is None:
                child = node.children[name] = Node(is_file=False)
            elif child.is_file:
                return None
            node = child
        return node

    def mkdir(self, path):
        return self._make_dirs(split(path)) is not None

    def write(self, path, text):
        parts = split(path)
        if not parts:
            return False
        parent = self._make_dirs(parts[:-1])
        if parent is None:
            return False
        node = parent.children.setdefault(parts[-1], Node(is_file=True))
        if not node.is_file:
            return False                           # a directory already has this name
        node.content += text
        return True

    def cat(self, path):
        node = self._find(split(path))
        return node.content if node is not None and node.is_file else None

    def ls(self, path):
        parts = split(path)
        node = self._find(parts)
        if node is None:
            return None
        return [parts[-1]] if node.is_file else sorted(node.children)

    def rm(self, path):
        parts = split(path)
        parent = self._find(parts[:-1]) if parts else None
        if parent is None or parent.is_file or parts[-1] not in parent.children:
            return False
        del parent.children[parts[-1]]             # a directory goes with everything in it
        return True

    def find(self, path, ext):
        # Every file at any depth under path whose name ends with "." + ext.
        start = self._find(split(path))
        found, stack = [], [] if start is None else [(start, "/" + "/".join(split(path)))]
        while stack:
            node, full = stack.pop()
            if node.is_file:
                if full.endswith("." + ext):
                    found.append(full)
            else:
                for name, child in node.children.items():
                    stack.append((child, full.rstrip("/") + "/" + name))
        return sorted(found)

    def du(self, path):
        # Total size of the files under path.
        start = self._find(split(path))
        total, stack = 0, [] if start is None else [start]
        while stack:
            node = stack.pop()
            if node.is_file:
                total += len(node.content)
            else:
                stack.extend(node.children.values())
        return total

#include <algorithm>
#include <map>
#include <memory>
#include <optional>
#include <sstream>
#include <string>
#include <utility>
#include <vector>
using namespace std;

struct Node {
    bool is_file;
    string content;                              // for a file
    map<string, unique_ptr<Node>> children;      // for a directory, kept sorted by name
    explicit Node(bool is_file) : is_file(is_file) {}
};

vector<string> split(const string& path) {        // "/a//b/" -> {"a", "b"}
    vector<string> parts;
    stringstream ss(path);
    string part;
    while (getline(ss, part, '/'))
        if (!part.empty()) parts.push_back(part);
    return parts;
}

class FileSystem {
    Node root{false};

    // Walk existing nodes only. nullptr if missing or a file is in the way.
    Node* find_node(const vector<string>& parts, size_t count) {
        Node* node = &root;
        for (size_t i = 0; i < count; i++) {
            if (node->is_file) return nullptr;
            auto it = node->children.find(parts[i]);
            if (it == node->children.end()) return nullptr;
            node = it->second.get();
        }
        return node;
    }

    // Create missing directories. nullptr (and no change) if a file is in the way.
    Node* make_dirs(const vector<string>& parts, size_t count) {
        Node* node = &root;
        for (size_t i = 0; i < count; i++) {
            auto& child = node->children[parts[i]];
            if (!child) child = make_unique<Node>(false);
            else if (child->is_file) return nullptr;
            node = child.get();
        }
        return node;
    }

public:
    bool mkdir(const string& path) {
        auto parts = split(path);
        return make_dirs(parts, parts.size()) != nullptr;
    }

    bool write(const string& path, const string& text) {
        auto parts = split(path);
        if (parts.empty()) return false;
        Node* parent = make_dirs(parts, parts.size() - 1);
        if (!parent) return false;
        auto& node = parent->children[parts.back()];
        if (!node) node = make_unique<Node>(true);
        if (!node->is_file) return false;        // a directory already has this name
        node->content += text;
        return true;
    }

    optional<string> cat(const string& path) {
        auto parts = split(path);
        Node* node = find_node(parts, parts.size());
        if (!node || !node->is_file) return nullopt;
        return node->content;
    }

    optional<vector<string>> ls(const string& path) {
        auto parts = split(path);
        Node* node = find_node(parts, parts.size());
        if (!node) return nullopt;
        if (node->is_file) return vector<string>{parts.back()};
        vector<string> names;
        for (auto& [name, child] : node->children) names.push_back(name);
        return names;
    }

    bool rm(const string& path) {
        auto parts = split(path);
        if (parts.empty()) return false;
        Node* parent = find_node(parts, parts.size() - 1);
        if (!parent || parent->is_file) return false;
        return parent->children.erase(parts.back()) > 0;   // a directory goes with everything in it
    }

    // Every file at any depth under path whose name ends with "." + ext.
    vector<string> find(const string& path, const string& ext) {
        auto parts = split(path);
        vector<string> found;
        Node* start = find_node(parts, parts.size());
        if (!start) return found;
        string base;
        for (auto& p : parts) base += "/" + p;
        vector<pair<Node*, string>> stack{{start, base}};
        string suffix = "." + ext;
        while (!stack.empty()) {
            auto [node, full] = stack.back();
            stack.pop_back();
            if (node->is_file) {
                if (full.size() >= suffix.size() && full.compare(full.size() - suffix.size(), suffix.size(), suffix) == 0)
                    found.push_back(full);
            } else {
                for (auto& [name, child] : node->children) stack.push_back({child.get(), full + "/" + name});
            }
        }
        sort(found.begin(), found.end());
        return found;
    }

    // Total size of the files under path.
    long long du(const string& path) {
        auto parts = split(path);
        Node* start = find_node(parts, parts.size());
        long long total = 0;
        vector<Node*> stack;
        if (start) stack.push_back(start);
        while (!stack.empty()) {
            Node* node = stack.back();
            stack.pop_back();
            if (node->is_file) total += node->content.size();
            else for (auto& [name, child] : node->children) stack.push_back(child.get());
        }
        return total;
    }
};

import java.util.*;

class FileSystem {
    static class Node {
        final TreeMap<String, Node> children;      // for a directory, sorted by name; null for a file
        final StringBuilder content = new StringBuilder();
        Node(boolean isFile) { children = isFile ? null : new TreeMap<>(); }
        boolean isFile() { return children == null; }
    }

    private final Node root = new Node(false);

    static List<String> split(String path) {       // "/a//b/" -> [a, b]
        List<String> parts = new ArrayList<>();
        for (String p : path.split("/")) if (!p.isEmpty()) parts.add(p);
        return parts;
    }

    // Walk existing nodes only. null if missing or a file is in the way.
    private Node find(List<String> parts, int count) {
        Node node = root;
        for (int i = 0; i < count; i++) {
            if (node.isFile()) return null;
            node = node.children.get(parts.get(i));
            if (node == null) return null;
        }
        return node;
    }

    // Create missing directories. null (and no change) if a file is in the way.
    private Node makeDirs(List<String> parts, int count) {
        Node node = root;
        for (int i = 0; i < count; i++) {
            Node child = node.children.computeIfAbsent(parts.get(i), k -> new Node(false));
            if (child.isFile()) return null;
            node = child;
        }
        return node;
    }

    boolean mkdir(String path) {
        List<String> parts = split(path);
        return makeDirs(parts, parts.size()) != null;
    }

    boolean write(String path, String text) {
        List<String> parts = split(path);
        if (parts.isEmpty()) return false;
        Node parent = makeDirs(parts, parts.size() - 1);
        if (parent == null) return false;
        Node node = parent.children.computeIfAbsent(parts.get(parts.size() - 1), k -> new Node(true));
        if (!node.isFile()) return false;          // a directory already has this name
        node.content.append(text);
        return true;
    }

    String cat(String path) {
        List<String> parts = split(path);
        Node node = find(parts, parts.size());
        return node != null && node.isFile() ? node.content.toString() : null;
    }

    List<String> ls(String path) {
        List<String> parts = split(path);
        Node node = find(parts, parts.size());
        if (node == null) return null;
        if (node.isFile()) return List.of(parts.get(parts.size() - 1));
        return new ArrayList<>(node.children.keySet());
    }

    boolean rm(String path) {
        List<String> parts = split(path);
        if (parts.isEmpty()) return false;
        Node parent = find(parts, parts.size() - 1);
        if (parent == null || parent.isFile()) return false;
        return parent.children.remove(parts.get(parts.size() - 1)) != null;   // with everything in it
    }

    // Every file at any depth under path whose name ends with "." + ext.
    List<String> findByExtension(String path, String ext) {
        List<String> parts = split(path);
        List<String> found = new ArrayList<>();
        Node start = find(parts, parts.size());
        if (start == null) return found;
        Deque<Object[]> stack = new ArrayDeque<>();
        stack.push(new Object[]{start, parts.isEmpty() ? "" : "/" + String.join("/", parts)});
        while (!stack.isEmpty()) {
            Object[] top = stack.pop();
            Node node = (Node) top[0];
            String full = (String) top[1];
            if (node.isFile()) {
                if (full.endsWith("." + ext)) found.add(full);
            } else {
                for (Map.Entry<String, Node> e : node.children.entrySet())
                    stack.push(new Object[]{e.getValue(), full + "/" + e.getKey()});
            }
        }
        Collections.sort(found);
        return found;
    }

    // Total size of the files under path.
    long du(String path) {
        List<String> parts = split(path);
        Node start = find(parts, parts.size());
        long total = 0;
        Deque<Node> stack = new ArrayDeque<>();
        if (start != null) stack.push(start);
        while (!stack.isEmpty()) {
            Node node = stack.pop();
            if (node.isFile()) total += node.content.length();
            else stack.addAll(node.children.values());
        }
        return total;
    }
}

A flat map instead of a tree

When a problem only needs files (no empty folders, no folder sizes), a dict from full path to file is enough: ls becomes “every key that starts with folder + '/'”, which is O(all files) per call. Cloud storage OAs often start this way. Once a level asks for folders, sizes per folder or fast listing, the tree pays for itself.

Why it’s O(depth)

Find and make-directories take one map lookup per name: O(d) for a path of depth d (plus the time to hash each name). ls sorts the children, O(c log c) for c children, or O(c) with a sorted map like Java’s TreeMap or C++’s std::map. rm is O(d) to find the parent, then O(1) to unlink the whole subtree. Python and Java reclaim the memory later; in C++ the destructors free the subtree right away, which is O(subtree). Find-by-extension and du visit every node under the start: O(subtree size), plus sorting the results.

operation	cost
`mkdir`, write, read	O(depth)
`ls`	O(depth + c log c)
`rm` (any size)	O(depth) to unlink
find, total size	O(nodes in the subtree)

If a folder’s total size is asked for constantly, store a running size on every directory and update the whole chain of parents on each write: O(depth) per write, O(1) per query.

Common mistakes

Splitting without dropping empty parts

"/a/b".split("/") is ["", "a", "b"], and "/a//b/" has more empty strings. Using them as names creates a directory called "".

parts = path.split("/")                         # ✗ ['', 'a', 'b']
parts = [p for p in path.split("/") if p]       # ✓ ['a', 'b']

Walking into a file

If the walk doesn’t check whether the current node is a file, /docs/cv.txt/x.txt either crashes or quietly turns a file into a folder.

node = node.children[name]                      # ✗ files have no children
if node.is_file or name not in node.children: return None   # ✓

Creating folders and then failing

If write creates /a/b and only then finds that the final name is a directory, the call fails but leaves new folders behind. Check everything that can fail before creating, or create only after the last existing name, as here.

mkdirs(parts); if is_dir(path): return False    # ✗ folders already made
parent = self._make_dirs(parts[:-1])            # ✓ fails before creating anything

Matching an extension without the dot

name.endswith("jpg") matches a file called jpg and one called notajpg. The extension is what follows the last dot.

if name.endswith(ext): ...                      # ✗ "jpg" and "xjpg" match
if name.endswith("." + ext): ...                # ✓ only ".jpg"

Variations

Sizes and capacity. Files carry sizes, and users have quotas: keep a per-user total and check it before any write that would grow it, so a refused write changes nothing.
Copy and move. Copy is a deep copy of a subtree; move is detach from one parent and attach to another. Refuse a move into the node’s own subtree.
Ranking results. “Largest first, then by path” is a sort key: (-size, path).
Wildcards and globbing. Walk the tree, matching each path component against its pattern; ** matches any number of folders.
Real files. For files on disk, os.walk or pathlib.Path.rglob do the subtree walk, and the file deduplication guide builds on them.

Climb the ladder

Our file-system problems in ladder order.

Directory tree from paths: nested maps, listing and folder sizes.
Camera card: find by extension, delete folders: subtree walks and recursive delete.
Design In-Memory File System: the classic ls, mkdir, write and read.
Cloud file storage: a flat store of paths, then search, users with capacity, and compression.

Check yourself

5 quick questions. Pick an answer to see why it's right or wrong.

1
What does this print?
```
path = "/a//b/"
print(path.split("/"), [p for p in path.split("/") if p])
```
split("/") keeps an empty string before the leading slash, between the two slashes and after the trailing one. Used as names, those would create a directory called "". Filtering out empty parts makes /a//b/ and /a/b the same path.
2
A file system’s ls is called far more often than files are created, and must list a folder’s children in name order. How should each directory store its children?
A sorted map hands back the names in order in O(c), with O(log c) inserts. A hash map sorts on every listing, O(c log c) each time; creation order isn’t name order; and a global path dict makes listing a folder a scan of every path in the system.
3
Which names count as .jpg files? What does this print?
```
names = ["a.jpg", "jpg", "b.jpeg", "c.tar.jpg", "xjpg"]
print(sum(n.endswith("jpg") for n in names), sum(n.endswith(".jpg") for n in names))
```
Without the dot, jpg and xjpg also match, giving 4. With it, only a.jpg and c.tar.jpg match: the extension is what follows the last dot, so c.tar.jpg counts and b.jpeg doesn’t.
4
Folder /a exists, and /a/b is a file. What should write("/a/b/c.txt", "hi") do?
A file can’t contain anything, so the path is invalid. The walk must notice that b is a file and stop before creating anything, so a refused call leaves the tree exactly as it was. Overwriting the file would silently destroy data.
5
du(folder) (total size of the files under a folder) is called 100,000 times on a tree of 100,000 files, and writes are rare. What’s the best design?
A write changes the sizes of the folders on its path only, so updating those O(depth) ancestors keeps every folder’s size exact, and du becomes O(depth) to find the folder. Walking the subtree is O(n) per query, a cache that’s never updated goes stale, and the root total is right only for the root.

Practice problems

Solve these right here, in Python, C++ or Java. Tests run as you go.