蛋蛋自以为搞清楚了货物标签的来龙去脉，突然他发现了一个重要的问题：货物的名字在哪里？是啊，标签inode里面那么多东西，为什么偏偏没有货物的名字呢？那么文件名到底藏在哪里，蛋蛋带着疑问继续翻盒子，终于找到了真相。
话说古代有个人，拿着马经去找马，按照图纸牵了一匹马回来，没想到大家发现他找到的是一只大蟾蜍！这就是上面这张图，按图索骥的故事，讽刺刻板按照图纸做事，但其实应该怪写马经的人，写得不严谨，不精确，让人找到错的东西。Linux市经济发达，货物众多，仅仅取个名很容易混淆，而且也不好管理。饿想她超市的人为了精确的表示每一个货物，给每个货物按个名字的同时，还加了个目录，每个目录里面有文件，也有目录，最上面是个根目录，这样，从根目录出发，一级级找下去，就能找到最终的货物。
路径Dentry
如下图，要找一个文件/var/test.txt，这条路有两条路径，/->var，var -> test.txt，合起来就成了完整的路。每一个目录有一个inode，同时也有dentry。先拿到根目录/的dentry，得到它的inode地址，从inode又知道了data block位置，data block里面是个大数组，依次放着所有这个目录里面一级目录和文件的dentry。把var和每一个dentry的文件名一一比较，就找到了var的dentry，按同样的方法，继续重新开始，最终就找到了test.txt的数据盒子block了。
- 通过根目录/的dentry得到inode 2，到目录盒子和每个dentry比较，发现var的dentry；
- 找到var的inode 10747905，到目录盒子和每个dentry比较，发现test.txt的dentry；
- 找到test.txt的inode，知道了所有的数据盒子位置，可以访问数据了。
Dentry的内容如下，主要是文件名和inode的编号。
Hash Tree快速查找
了解到这里，蛋蛋真是烦透了:买个东西这么麻烦啊！要在每个dentry的盒子里面和所有下一级dentry一个个比较，真是累死人了！还想不想做生意了，搞得哥不爽，去别家买了。扭头便走，走到门口又停下来了：我是不是低估了饿想她超市的智商，他们生意做得这么好，肯定不会一直用这么麻烦的流程。蛋蛋又回去逛了逛:原来前面那一套都是旧的超市用的过时的方法，最近新开的店都用了更先进的方法：Hash Tree。什么，又是一棵树，你们超市工程师以前都是种树的吧？
如下图，根目录的盒子里面是个表，每个路径用hash算法算出一个hash值，每个hash值有一个自己的盒子，里面是所有的dentry，如果多个路径是同样的hash值，那么就在这个hash的盒子里面放所有的dentry。这样，最快查一次就查到一个路径的dentry了，毕竟hash重复的概率还是不大的。
每个hash条目的内容如下，32位Hash值和对应的盒子地址。
引用
https://ext4.wiki.kernel.org/index.php/Ext4_Disk_Layout
http://www.cnblogs.com/vamei/p/3506566.html
http://oldblog.donghao.org/2011/03/ext3adir-indexioo.html
想要每天看一条SSD文章吗？扫一扫，微信关注我们！或者微信搜索公众号ssdfans关注。
