看这边死程挺多的，问个数据结构的问题

两点水 · 发表于 2011-7-20 12:02

我想写个 launchy 那种程序启动器，索引了文件列表之后在内存里用什么结构储存合适呢？

有几个主要的需求：增量搜索（就是数据筛选），结果排序，内存占用不要太大

现在是用 sqlite 实现的，但是库文件有点大，我想生成一个尽量小的执行文件所以目前用的是纯 c

yipansansha · 发表于 2011-7-20 12:26

排序文件大小用quicksort，没有额外内存开销，根据文件大小分布选择要不要随机

文件名用radix sort
==
增量搜索可以用radix sort完成之后根据结果来做

比如叶子节点放实际数据，中间节点不放，每一个节点放最多前10个（随便多少）实际数据的指针。

不知道跑题没

venusvsvirus · 发表于 2011-7-20 14:14

文件索引上b+树

两点水 · 发表于 2011-7-20 15:07

多谢两位，先补充一下，我的排序只根据文件名和一个外部输入的值（优先级），所以 quick sort 用不上

不知道这种多条件的排序用基数排序或者 B+ 树能不能做到？

花剑酒 · 发表于 2011-7-20 15:11

死程帖都好高深。

yipansansha · 发表于 2011-7-20 15:19

B+树的好处是平衡和兼顾顺序，不过平衡这个思路ms是给文件系统随机搜索设计的

要排序radix sort就是你说的基数排序吧？把优先级作为文件名前缀，从后向前按文件名的每个字符做counting sort就是radix了。

之前说麻烦了，数据可以用链表存，索引做成分叉数固定的决策树（只是少了B+平衡的操作好像）

venusvsvirus · 发表于 2011-7-20 16:08

你说的外部参数实际上就是按调用频率给的权重吧？B+数存储的时候只以文件名为比较因子。搜索结果取一定范围内的子b数，所有子节点存入数组，将离中心（即你搜索文件名的字符串最匹配的节点）的远近和调用频率分别赋予一个权重快排。

刚才手滑打错了...

venusvsvirus · 发表于 2011-7-20 16:43

从子树构造搜索结果的数组近乎天然有序，而且n不大，似乎用插入排序还更好一点

或者保持原顺序然后取外部参数做优先级构造优先队列会比较好？

鸡蛋灌饼 · 发表于 2011-7-20 16:47

引用第5楼yipansansha于2011-07-20 15:19发表的回 3楼(两点水) 的帖子 :
B+树的好处是平衡和兼顾顺序，不过平衡这个思路ms是给文件系统随机搜索设计的

要排序radix sort就是你说的基数排序吧？把优先级作为文件名前缀，从后向前按文件名的每个字符做counting sort就是radix了。

之前说麻烦了，数据可以用链表存，索引做成分叉数固定的决策树（只是少了B+平衡的操作好像）

B+主要处理的是外部排序吧
全在内存操作那就上红黑树好了，或者用STL容器

另外，相比GUI那堆东西，CRT什么的还真不算大家伙……

venusvsvirus · 发表于 2011-7-20 16:51

楼主的意思是要建文件索引吧，索引肯定是在硬盘上的。。。需要再排序的只是搜索结果吧。。。

两点水 · 发表于 2011-7-20 17:03

引用第9楼venusvsvirus于2011-07-20 16:51发表的 :
楼主的意思是要建文件索引吧，索引肯定是在硬盘上的。。。需要再排序的只是搜索结果吧。。。

是的，看来我的问题不够明确。
就是在内容最终会索引到硬盘上的情况下，用哪种数据结构合适。
目前我是单纯用 api 把文件列表输出到文件里，然后调用程序时再读到链表里排序，感觉这样很蠢。

venusvsvirus · 发表于 2011-7-20 17:07

引用第10楼两点水于2011-07-20 17:03发表的 :

是的，看来我的问题不够明确。
就是在内容最终会索引到硬盘上的情况下，用哪种数据结构合适。
目前我是单纯用 api 把文件列表输出到文件里，然后调用程序时再读到链表里排序，感觉这样很蠢。

我6楼7楼给了建议了，我能想到的最好的解决方案了。请问你是做哪个平台，mac可以调用系统的spotlight索引不用自己来，win7应该也可以吧，查查api也许能避免重造轮子

鸡蛋灌饼 · 发表于 2011-7-20 17:12

引用第10楼两点水于2011-07-20 17:03发表的 :

是的，看来我的问题不够明确。
就是在内容最终会索引到硬盘上的情况下，用哪种数据结构合适。
目前我是单纯用 api 把文件列表输出到文件里，然后调用程序时再读到链表里排序，感觉这样很蠢。

索引内容是文件路径？
用Radix tree，当然还有其他很多方法可以考虑
如果要向Everything一样迅速的话索引全读进内存是不可避免的，这时候就别过多考虑磁盘上的东西怎么存了

引用第11楼venusvsvirus于2011-07-20 17:07发表的 :

我6楼7楼给了建议了，我能想到的最好的解决方案了。请问你是做哪个平台，mac可以调用系统的spotlight索引不用自己来，win7应该也可以吧，查查api也许能避免重造轮子

Windows：Everything
*nix：locate+updatedb
Mac就是你说的

不过我真不觉得能怎么优化——特别是如果要加通配符或正则表达式支持的话

yaksayahc · 发表于 2011-7-20 17:20

建立索引的时候就考虑排序不可以么？GIT的refs存储就是这种思路，所有refs的名字都是sha1字符串，然后用sha1字符串的头几位建立一级目录，在一级目录下面建立文件名。要索引大量文件，完全可以考虑把文件名截断成多截建立多级索引哇。至于实时排序...说实在的，对即时响应的系统，任何大数据上的实时排序都应该是避免的，尽量早做indexing才是正途。

两点水 · 发表于 2011-7-20 17:26

引用第5楼yipansansha于2011-07-20 15:19发表的回 3楼(两点水) 的帖子 :
B+树的好处是平衡和兼顾顺序，不过平衡这个思路ms是给文件系统随机搜索设计的

要排序radix sort就是你说的基数排序吧？把优先级作为文件名前缀，从后向前按文件名的每个字符做counting sort就是radix了。

之前说麻烦了，数据可以用链表存，索引做成分叉数固定的决策树（只是少了B+平衡的操作好像）

谢谢，看来树型结构是必须了。另外我想问一下，因为要做增量搜索,如果用链表处理链表就要反复被查找（做字符串比较），这样的话是不是还是树合适？

引用第11楼venusvsvirus于2011-07-20 17:07发表的 :

我6楼7楼给了建议了，我能想到的最好的解决方案了。请问你是做哪个平台，mac可以调用系统的spotlight索引不用自己来，win7应该也可以吧，查查api也许能避免重造轮子

没想到发帖的时候内容又增加了……
mac 下那个 spotlight 太慢被我关了
windows 下倒是有 usn journal，但是受磁盘类型限制（只能 ntfs）
谢谢你给出的逻辑，我觉得用树结构然后对查找结果再单独按权排序确实是不错的办法。

ps.我知道这挺贱的但是因为我本身就是用多系统所以写程序的时候想尽量少用系统特性（死

另外还有两个问题：

1，我现在比较头痛的就是文件有变动我的索引文件就要更新，我很希望能在保留原索引的基础上更新文件变动，请问这样可不可行？
2，程序内部如果全用 utf8 处理会不会比 wchar_t 好一点（综合效率和实现难度），我现在全用双字节但感觉有点浪费。

venusvsvirus · 发表于 2011-7-20 17:30

用树建立索引就是为了查找方便，但是每次调用频率的变更就变动整个树结构很不划算，况且以后还可能有根据修改时间排序之类的需求，所以我觉得树里面的比较因子只用文件名好点，但是正则搜索确实是个问题，也不是不能做，只是这个字符串比较算法要好好琢磨琢磨了。。。。

另外貌似系统的索引动则几g这些在搜索的时候真的全部进内存吗?

鸡蛋灌饼 · 发表于 2011-7-20 17:42

引用第14楼两点水于2011-07-20 17:26发表的 :

没想到发帖的时候内容又增加了……
mac 下那个 spotlight 太慢被我关了
windows 下倒是有 usn journal，但是受磁盘类型限制（只能 ntfs）
.......

你这个东西和我现在正在做的有点像，我就把我的Design Choices说一下吧：
1. 不要考虑高效的FAT支持，FAT这货的设计决定了扫描一个FAT分区的代价是不可接受的
2. 为了性能，一定要挖掘系统特性，NTFS必须扫描MFT和Journal，否则还不如IPC用Everything；Linux也一样，fanotify和libe2fs都要列入考虑
3. USN Journal和fanotify是增量变更的好帮手
4. 使用Native Unicode实现，Windows下用wchar_t存UTF16，Linux下用char存UTF-8，不然这俩东西的转换也能玩死你
5. [win32]尽可能调用Unicode版本的API（blablablaW），我现在都是直接把W后缀写死在程序里，不能让MangaMeeya的悲剧再度上演。

引用第15楼venusvsvirus于2011-07-20 17:30发表的 :

另外貌似系统的索引动则几g这些在搜索的时候真的全部进内存吗?

我这里Everything的数据库不过5MB，进程内存占用最多60M左右
退一步：如果一个文件系统的索引竟然上G（对于一个T以下的磁盘），那么这个文件系统的设计者是不是可以去死了……

yipansansha · 发表于 2011-7-20 17:55

你们好喜欢自平衡……

==

还是看哪个需求多吧，如果那个增量搜索不重要，结果不是全部列举的话，树都不要做，每次可以在线性STL里2分查找合理结果的开头和结尾

全都列举的话，建自平衡树会好不少，但写搜索结果时至少要对中间节点的字符串整串比较，而不是单个位比较。吃内存是O(数据总量/分叉数)总root开始走每次要花 (比较整串的时间)* log n，找出开头结尾

至于radix tree，先从前向后过一遍把树做出来（文件夹名字固定，就做hash），比如文件夹名字相同就做为一个整体hash，文件名字不同的话，那就一位一位展开。每个中间的节点，都含有一个{叶子节点总量m}的数据, 搜索的时候，log n步骤的hash或者单字符比较，锁定到具体STL里面的某个元素之后，iterator走m步即可，不需要比较。

==

我好像没说清LZ加油，看了楼上们表示我可以去预习文件系统了

venusvsvirus · 发表于 2011-7-20 18:25

我这里Everything的数据库不过5MB，进程内存占用最多60M左右
退一步：如果一个文件系统的索引竟然上G（对于一个T以下的磁盘），那么这个文件系统的设计者是不是可以去死了……

貌似是我搞错了.... 不知道为什么总有索引很吃硬盘的错觉

mac 下那个 spotlight 太慢被我关了

spotlight在我用过的文件搜索中比win7和KDE的搜索都要快啊

1，我现在比较头痛的就是文件有变动我的索引文件就要更新，我很希望能在保留原索引的基础上更新文件变动，请问这样可不可行？

win和Linux楼上说了，mac比较奇葩，HFS+并不是所有人都开了日志功能，保守的做法是用系统的fsevent,性能就

了

venusvsvirus · 发表于 2011-7-20 18:30

你们好喜欢自平衡……

B+的优势不是自平衡，而是层次极简，虽然都是Olog(n)但其实性能差别很大

鸡蛋灌饼 · 发表于 2011-7-20 18:53

引用第18楼venusvsvirus于2011-07-20 18:25发表的 :

貌似是我搞错了.... 不知道为什么总有索引很吃硬盘的错觉

你印象中的那个应该是全文索引，这东西肯定大……

		自动登录	找回密码
密码			立即注册

[软件] 看这边死程挺多的，问个数据结构的问题

回 3楼(两点水) 的帖子

Re:回 3楼(两点水) 的帖子

回 12楼(鸡蛋灌饼) 的帖子

浏览过的版块