我想要一个聪明的文件目录索引算法……指针？

Question

我在Ubuntu上有一个音乐文件夹，里面有很多音乐文件（比如.mp3、.wav等）。这个文件夹可以有很多子文件夹，没有限制。我想把这些音乐整理成一个音乐库，也就是说，我希望能根据以下条件返回歌曲列表：

1) 播放列表中的歌曲 2) 艺术家名字 3) 字符串搜索 4) 歌曲名称 等等等等

但是，如果文件名被更改、文件被移动，或者我的音乐文件夹里添加了新文件，我需要能够快速更新我的音乐管理系统，以反映这些变化！

我最开始想用pyinotify、incron或inotify来监控我的文件夹。不幸的是，我的文件夹是一个Samba共享，所以监控文件事件就失败了。接下来，我想到了用Python递归搜索这个文件夹，然后把信息存入一个SQL数据库。更新的时候，我只需要查看是否有任何变化（扫描每个子文件夹，看看每首歌的名字是否已经在数据库里，如果没有就添加进去），然后相应地进行更新。不幸的是，这样的做法似乎效率很低，复杂度是O(n^2)，对于一个多TB的音乐收藏来说，这实在太糟糕了。

一个稍微好一点的办法可能是创建一个SQL树结构，这样在每个子文件夹中查找匹配项时，可以缩小搜索范围到那个子文件夹的大小。不过，这样的做法还是显得不够优雅。

我可以用什么设计思路或工具来帮助自己呢？显然，这会涉及到很多聪明的哈希表。我只是想找一些合适的方向，来处理这个问题。（另外，我非常喜欢优化。）

Answer 1

实际上，这个问题是个难题。你一开始就处于劣势，因为Python和mySQL并不是处理这个问题的最快工具。

就连iTunes也常常被抱怨，因为它导入库和索引新文件的速度很慢。你能想象为了让iTunes变得这么好，投入了多少人力吗？

你最好的选择是看看一些主要的开源音乐播放器的代码，比如：

• Miro，http://www.getmiro.com/，
• Banshee，http://banshee.fm/，还有
• Songbird，http://getsongbird.com/

然后尝试把它们的算法调整到你的需求上，并适应Python的写法。

Answer 2

我的 aggregate_digup 程序可以读取一种特殊格式的文件，这种文件是由 digup 程序生成的，里面包含了文件的 sha1 校验和。这让我可以根据文件的 sha1 校验和来找到文件。digup 程序在输出中记录了文件的修改时间、大小、哈希值和路径。默认情况下，如果文件的修改时间和大小匹配，它就会跳过对文件的哈希计算。我的 aggregate_digup 生成的索引被我修改过的 gedit 插件使用，这个插件可以让你在上下文菜单中通过选项点击 sha1:b7d67986e54f852de25e2d803472f31fb53184d5，然后列出它知道的文件副本，你可以选择一个来打开。

这个内容和问题的关系在于有两个部分：一个是播放列表，另一个是文件。

如果我们假设播放器的操作不会改变文件，那么文件的哈希值和大小就是固定的。因此，我们应该可以用文件的大小和哈希值作为唯一标识符。

比如，提到的文件的键是： 222415:b7d67986e54f852de25e2d803472f31fb53184d5

我发现，在实际使用中，这种方法在任何自然的集合中都不会出现重复。

（这意味着，如果你选择在哈希时跳过 ID3 元数据，那么附加在 mp3 数据前后的元数据就不能改变）

所以播放列表数据库可能是这样的：

files(file_key, hash, size, mtime, path, flag)
tracks(file_key, title, artist)
playlists(playlistid, index, file_key)

要更新文件表：

import os
import stat
# add new files:
update files set flag=0
for path in filesystem:
    s=os.stat(path)
    if stat.S_ISREG(s.st_mode):
        fetch first row of select mtime, hash, size from files where path=path
        if row is not None:
            if s.st_mtime == mtime and s.st_size == size:
                update files set flag=1 where path=path
                continue
        hash=hash_file(path)
        file_key="%s:%s" % (int(s.st_mtime), hash)
        insert or update files set file_key=file_key, size=s.st_size, mtime=s.st_mtime, hash=hash, flag=1 where path=path
# remove non-existent files:
delete from files where flag=0

Answer 3

这段内容的难点在于扫描目录，因为这个过程可能会很耗时。

但这就是现实，因为你不能使用 inotify 等工具。

在你的数据库里，简单地创建一个节点类型的记录：

create table node (
    nodeKey integer not null primary key,
    parentNode integer references node(nodeKey), // allow null for the root, or have root point to itself, whatever
    fullPathName varchar(2048),
    nodeName varchar(2048),
    nodeType varchar(1) // d = directory, f = file, or whatever else you want
)

这就是你的节点结构。

你可以用完整路径的列来快速找到任何文件，只需提供绝对路径。

当文件移动时，只需重新计算路径即可。

最后，扫描你的音乐文件。在 Unix 系统中，你可以这样做：

find . -type f | sort > sortedListOfFiles

接下来，从数据库中提取所有路径名称。

select fullPathName from node where nodeType != 'd' order by fullPathName

现在你有了两个已排序的文件列表。

用 DIFF（或 comm）对比它们，你就能得到被删除和新增文件的列表。不过，你不会得到“移动”文件的列表。如果你想通过比较新旧文件的路径（比如 ..../album/song）来尝试检测“移动”文件和新旧文件，那也没问题，值得一试。

不过，diff 会很快给你差异结果。

如果你有成千上万的文件，那就抱歉，这会花一些时间——但你已经知道失去 inotify 功能后会这样。如果有这个功能，那就只需要增量维护了。

当文件移动时，找到它的新绝对路径非常简单，因为你可以询问它的父目录获取路径，然后直接把文件名加上去。之后，你就不需要遍历树结构，除非你想这样做。这个方法是双向的。

补充说明：

如果你想追踪实际的文件名变化，你可以获取更多信息。

你可以这样做：

find . -type f -print0 | xargs -0 ls -i | sort -n > sortedListOfFileWithInode

其中 -print0 和 -0 是用来处理文件名中有空格的情况。不过，如果文件名中有引号，这会导致问题。你可能更好地通过 Python 和 fstat 来处理原始列表，以获取 inode。这里有很多不同的做法。

这样做的好处是，除了文件名，你还可以获得文件的 inode。inode 是“真实”的文件，目录将文件名链接到 inode。这就是为什么在 Unix 文件系统中，一个文件可以有多个名字（硬链接），所有名字都指向同一个 inode。

当文件被重命名时，inode 会保持不变。在 Unix 中，有一个单一的命令用于重命名和移动文件，那就是 mv。当 mv 重命名或移动文件时，只要文件在同一个文件系统上，inode 就会保持不变。

因此，使用 inode 和文件名可以让你捕捉到更有趣的信息，比如文件移动。

如果文件被删除并添加了一个新文件，这个方法就没用了。但你很可能能知道这种情况发生了，因为旧的 inode 不太可能会被新 inode 重用。

所以如果你有一个文件列表（按文件名排序）：

1234 song1.mp3
1235 song2.mp3
1236 song3.mp3

如果有人删除并重新添加了第二首歌，你会得到类似这样的结果：

1234 song1.mp3
1237 song2.mp3
1236 song3.mp3

但如果你这样做：

mv song1.mp3 song4.mp3

你会得到：

1237 song2.mp3
1236 song3.mp3
1234 song4.mp3

另一个需要注意的是，如果你丢失了驱动器并从备份中恢复，所有的 inode 很可能都会改变，这样就需要重新构建你的索引。

如果你真的很有冒险精神，可以尝试玩玩扩展文件系统属性，为文件分配其他有趣的元数据。我没有做过太多这方面的事情，但这也是有可能的，虽然可能会有一些看不见的风险，不过……