据我所知，一旦找到文件的索引节点，查找数据就很简单了——通过访问磁盘上存储在索引节点中的特定位置来完成。
然而问题是，当给系统一个文件路径时，到底是如何找到索引节点的？
我的问题的目的主要是希望了解 B 树在现实生活中的实现方式。我了解它的总体思路，但我想知道它在 Unix 文件系统中到底是如何实现的（如果有的话）。
树的每个节点是否存储 inode 编号，叶子还存储 inode 本身的磁盘上的地址吗？或者也许是文件路径的连续部分？
实施是否会根据磁盘是硬盘驱动器还是 SSD 而有所不同？
答案1
恕我直言：你有两个问题：
当给系统提供文件路径时，如何准确地找到索引节点
和
渴望掌握 B 树在现实生活中的实现方式。
也许您的问题是：inode 是如何存储的（在 b 树中），或者 inode 引用的数据。如果是这样，我无法回答。
就您的第一个字面问题而言，答案取决于操作系统，范围从not difficult到opaque。经典的系统调用（open、unlink）将读取目录以查找文件名条目 - 并将启动（在现代 - 通过调用 opendir()）。
在经典 UNIX 中 - 文件名的最大长度为 14 个字符 - 为 inode 留下 2 个字节（目录条目为 16 个字节）。没有（而且仍然没有）文件名和 inode 的 b 树组织 - 搜索是（并且是？）目录的串行读取。这属于simple需要检查的范畴。
即使在当今的系统上（允许使用更长的文件名），目录条目的基本外观也可能不会改变 - 2 字节（索引节点）、14 字节（初始文件名/完整文件名）。 （至少在 AIX 上 - 一切 - 甚至目录都遵循 UNIX 惯用语：一切都是文件，有些是特殊的。）
michael@x071:[/home/michael]ls -lia /tmp | head
total 287464
2 drwxrwxrwt 54 bin bin 36864 Jan 22 13:35 .
2 drwxr-xr-x 39 root system 4096 Jan 5 12:27 ..
5 drwxrwxrwt 2 root system 256 May 8 2013 .X11-unix
6 -rw-r----- 1 root system 0 May 23 2014 .ahafs.out.michael.10223652
7 -rw-r----- 1 root system 0 May 23 2014 .ahafs.out.michael.9502870
8 -r--r--r-- 1 root system 25 Jun 9 2013 .aix_ISMP_lock____.save
9 drwxrwxrwt 3 root system 4096 Dec 27 12:15 .com_ibm_tools_attach
62 -rw-r--r-- 1 root system 3124 Dec 27 11:21 .ctinst.log
63 -rw-r----- 1 michael felt 2578 Aug 16 2013 .htaccess
michael@x071:[/home/michael]od -dc /tmp | head -20
0000000 2 11776 0 0 0 0 0 0
\0 002 . \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0
0000020 2 11822 0 0 0 0 0 0
\0 002 . . \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0
0000040 32848 11895 28530 27492 26994 11825 13109 13878
200 P . w o r k d i r . 1 3 5 6 6
0000060 5 11864 12593 11637 28265 30720 0 0
\0 005 . X 1 1 - u n i x \0 \0 \0 \0 \0
0000100 6 11873 26721 26227 11887 30068 11885 26979
\0 006 . a h a f s . o u t . m i c
0000120 7 11873 26721 26227 11887 30068 11885 26979
\0 \a . a h a f s . o u t . m i c
0000140 8 11873 27000 24393 21325 20575 27759 25451
\0 \b . a i x _ I S M P _ l o c k
0000160 9 11875 28525 24425 25197 24436 28527 27763
\0 \t . c o m _ i b m _ t o o l s
0000200 62 11875 29801 28275 29742 27759 26368 0
\0 > . c t i n s t . l o g \0 \0 \0
0000220 63 11880 29793 25443 25971 29440 0 0
\0 ? . h t a c c e s s \0 \0 \0 \0 \0
注意：上面刚刚在 Linux 系统上尝试过 - 也许这些现在被组织为 B 树。不知道 - 因为我得到以下输出：
michael@x067:~$ od -dc /tmp|head
od: /tmp: read error: Is a directory
0000000
因此，传统上：inode“查找/映射”到（特殊）文件只是目录条目的前两个字节。索引节点要么位于磁盘上，要么存储在内存中，例如 b 树中。
在 AIX 中 - 'dirent' 结构在以下形式中“很容易找到”：
#define _D_NAME_MAX 255
struct dirent {
__ulong64_t d_offset; /* real off after this entry */
ino_t d_ino; /* inode number of entry */
ushort_t d_reclen; /* length of this record */
ushort_t d_namlen; /* length of string in d_name */
char d_name[_D_NAME_MAX+1]; /* name must be no longer than this */
/* redefine w/#define when name decided */
};
在 Linux（3.2.XY 内核）上 - 包含文件包含且结构为：
struct dirent
{
#ifndef __USE_FILE_OFFSET64
__ino_t d_ino;
__off_t d_off;
#else
__ino64_t d_ino;
__off64_t d_off;
#endif
unsigned short int d_reclen;
unsigned char d_type;
char d_name[256]; /* We must not include limits.h! */
};
两者 - 恕我直言 - 基本上是相同的 - 差异可以通过调用 readdir() 返回的方式来消除
Linux/GNU 方法：
/usr/include/dirent.h:
/* This is the data type of directory stream objects.
The actual structure is opaque to users. */
typedef struct __dirstream DIR;
注意：我无法找到 __dirstream 的任何内容 - 所以我添加了关于它的“评论”
opaque
extern DIR *opendir (__const char *__name) __nonnull ((1));
...
/* Read a directory entry from DIRP. Return a pointer to a `struct
dirent' describing the entry, or NULL for EOF or error. The
storage returned may be overwritten by a later readdir call on the
same DIR stream.
If the Large File Support API is selected we have to use the
appropriate interface.
This function is a possible cancellation point and therefore not
marked with __THROW. */
#ifndef __USE_FILE_OFFSET64
extern struct dirent *readdir (DIR *__dirp) __nonnull ((1));
#else
# ifdef __REDIRECT
extern struct dirent *__REDIRECT (readdir, (DIR *__dirp), readdir64)
__nonnull ((1));
# else
# define readdir readdir64
# endif
#endif
#ifdef __USE_LARGEFILE64
extern struct dirent64 *readdir64 (DIR *__dirp) __nonnull ((1));
#endif
在 AIX 上：
/*
* Definitions for library routines operating on directories.
*/
typedef struct _dirdesc {
#ifdef _ALL_SOURCE
int dd_fd; /* file descriptor of directory */
blksize_t dd_blksize; /* this filesystem's block size */
char *dd_buf; /* malloc'd buffer depending of fs bsize */
long dd_size; /* size of buffer */
long dd_flag; /* private flags for readdir, unused */
off_t dd_loc; /* logical(dirent) offset in directory */
off_t dd_curoff; /* real offset in directory corresponding
* to dd_loc */
#else
int __dd_fd; /* file descriptor of directory */
blksize_t __dd_blksize; /* this filesystem's block size */
char *__dd_buf; /* malloc'd buffer depending of fs bsize */
long __dd_size; /* size of buffer */
long __dd_flag; /* private flags for readdir, unused */
off_t __dd_loc; /* logical(dirent) offset in directory */
off_t __dd_curoff; /* real offset in directory corresponding
* to dd_loc */
#endif
#if defined(_THREAD_SAFE) && defined(_ALL_SOURCE)
void *dd_lock; /* for inter-thread locking */
#endif
} DIR;
...
extern DIR *opendir(const char *);
extern struct dirent *readdir(DIR *);
简而言之 - 恕我直言 - 根据操作系统的不同，结构on disk可能非常简单或opaque。在内核中，如果组织是opaque这样的我并不感到惊讶，那么你可以修改组织而不需要更改任何应用程序代码。