吊打面试官03:如何设计一个内存文件系统（多级目录）

//表结构
CREATETABLE categories (
  category_id INT PRIMARY KEY,
  parent_id   INTNULL,
  category_name TEXTNOTNULL,
FOREIGNKEY (parent_id) REFERENCES categories(category_id)
);
CREATEINDEX idx_categories_parent ON categories(parent_id);

//插入记录
INSERTINTO categories (category_id, category_name, parent_id) VALUES
(1, 'Electronics', NULL),
(2, 'Computers', 1),
(3, 'Laptops', 2),
(4, 'Desktops', 2),
(5, 'Smartphones', 1);

#include <vector>
#include <memory>

class CategoryNode {
public:
    int category_id;            // 节点ID（主键）
    std::string category_name; // 分类名称
    CategoryNode* parent;      // 指向父节点的指针（弱引用，避免循环强引用）
    std::vector<std::unique_ptr<CategoryNode>> children; // 子节点列表

    // 构造函数
    CategoryNode(int id, conststd::string& name, CategoryNode* parent_ptr = nullptr)
        : category_id(id), category_name(name), parent(parent_ptr) {}
};

class CategoryTree {
private:
    std::unique_ptr<CategoryNode> root; // 根节点
    std::unordered_map<int, CategoryNode*> node_map; // ID到节点的映射（加速查找）

public:
    // 添加节点（自动关联父子关系）
    void add_node(int id, const std::string& name, int parent_id) {
        CategoryNode* parent_ptr = (parent_id == -1) ? nullptr : node_map.at(parent_id);
        auto new_node = std::make_unique<CategoryNode>(id, name, parent_ptr);
        
        if (parent_ptr) {
            parent_ptr->children.push_back(std::move(new_node));
        } else { // 根节点
            root = std::move(new_node);
        }
        node_map[id] = node_map.empty() ? root.get() : parent_ptr->children.back().get();
    }
};

// 获取从根节点到当前节点的路径
std::vector<CategoryNode*> get_path(int id) {
    std::vector<CategoryNode*> path;
    CategoryNode* current = get_node(id);
    while (current) {
        path.push_back(current);
        current = current->parent;
    }
    std::reverse(path.begin(), path.end()); // 从根到当前
    return path;
}

// 查找所有后代节点（广度优先）
std::vector<CategoryNode*> get_descendants(int id) {
    std::vector<CategoryNode*> result;
    std::queue<CategoryNode*> queue;
    queue.push(get_node(id));
    while (!queue.empty()) {
        auto current = queue.front();
        queue.pop();
        for (constauto& child : current->children) {
            result.push_back(child.get());
            queue.push(child.get());
        }
    }
    return result;
}

https://github.com/ceph/ceph/blob/main/src/mds/CInode.h
//MDS内部数据结构
class CInode {
inodeno_t ino;
snapid_t snapid;
std::map<std::string, CDentry*> dentries; // children
  CInode* parent;         // pointer to parent directory
};
//OpenFileTable 结构加速恢复：记录打开文件的路径信息，避免全量加载
CInode (根目录) 
│
└── CDir (根目录内容)
    ├── CDentry ("a") ── CInode (目录"a")
    │               │
    │               └── CDir (目录"a"内容)
    │                   └── CDentry ("b.txt") ── CInode (文件"b.txt")
    │
    └── CDentry ("c") ── CInode (文件"c")

FileSystem fileSystem = new FileSystem();
fileSystem.ls("/");                         // 返回 []
fileSystem.mkdir("/a/b/c");
fileSystem.addContentToFile("/a/b/c/d", "hello");
fileSystem.ls("/");                         // 返回 ["a"]
fileSystem.readContentFromFile("/a/b/c/d"); // 返回 "hello"

#include <vector>
#include <string>
#include <unordered_map>
#include <set>
#include <sstream>
#include <algorithm>
usingnamespacestd;

class FileSystem {
private:
    // 文件系统节点结构
    struct FileNode {
        bool isFile = false;          // 是否为文件
        string content;                // 文件内容
        unordered_map<string, FileNode*> children; // 子节点映射
    };

    FileNode* root; // 根节点指针

    // 分割路径为组成部分
    vector<string> splitPath(const string& path) {
        vector<string> parts;
        if (path.empty() || path == "/") return parts;
        
        istringstream iss(path);
        string part;
        while (getline(iss, part, '/')) {
            if (!part.empty()) parts.push_back(part);
        }
        //
        return parts;
    }

    // 根据路径查找节点
    FileNode* traverse(const string& path) {
        if (path == "/") return root;
        
        vector<string> parts = splitPath(path);
        FileNode* current = root;
        for (conststring& part : parts) {
            if (!current->children.count(part)) returnnullptr;
            current = current->children[part];
        }
        return current;
    }

public:
    FileSystem() {
        root = new FileNode(); // 初始化根节点
    }

    vector<string> ls(const string& path) {
        FileNode* node = traverse(path);
        if (!node) return {};
        
        // 文件路径：返回文件名
        if (node->isFile) {
            int idx = path.find_last_of('/');
            return {path.substr(idx + 1)};
        }
        
        // 目录路径：返回排序后的子项名称
        vector<string> result;
        for (constauto& child : node->children) {
            result.push_back(child.first);
        }
        sort(result.begin(), result.end());
        return result;
    }

    void mkdir(string path) {
        vector<string> parts = splitPath(path);
        FileNode* current = root;
        
        for (conststring& part : parts) {
            if (!current->children.count(part)) {
                current->children[part] = new FileNode();
            }
            current = current->children[part];
        }
    }

    void addContentToFile(string filePath, string content) {
        vector<string> parts = splitPath(filePath);
        FileNode* current = root;
        
        // 确保目录路径存在
        for (int i = 0; i < parts.size() - 1; ++i) {
            if (!current->children.count(parts[i])) {
                current->children[parts[i]] = new FileNode();
            }
            current = current->children[parts[i]];
        }
        
        // 处理文件名
        string fileName = parts.back();
        if (!current->children.count(fileName)) {
            current->children[fileName] = new FileNode();
            current->children[fileName]->isFile = true;
        }
        current->children[fileName]->content += content;
    }

    string readContentFromFile(string filePath) {
        FileNode* node = traverse(filePath);
        if (node && node->isFile) {
            return node->content;
        }
        return"";
    }
};

std::istream& getline(std::istream& is, std::string& str, char delim);