装逼男的民工笔记之数据获取(data retrieval)

     上学期末一美女选课的时候让我跟她旁听“多媒体数据库和数据挖掘”，本着能跟这个美女多接触的心气，毅然决定蹭这门课。谁知拿到syllabus后，美女决然的放弃了这门课，于是哥们每堂课就只能对着一个操着俄罗斯口音的老教授欲哭无泪了。考虑到这面是哥们之后能在江湖上凑乎混的内力部分，勉强撑着听到现在，每节课就游走在不同树的变形，以及变形树的变形当中不知所云，所以就决心从这一科开始写起。
     上web的时候做过一个在线配对的网站，算法和数据库都简单的不行。 参考其他在线配对交友网站时基本也就是地域（geographic）,年龄范围(age range),等一些精确查找（ad hocquery）的属性。当时就有为什么没有模糊查询的功能的想法（比如长相要和哪个明星有多接近）。之后暑假实习做在线广告平台时，也遇到同样的问题，老板要模糊匹配，但那时确实不知道数据结构怎么弄，只能 hard-coding 关联律（Associative rules）到代码里。恰好这门课讲的结构都是解决这些问题的。所以做一总结。
       拿找美女来说，简单的查询（single query or adhoc query）像知道美女的名字，或只限定年龄范围，通过主键索引就可以有效的（时间和空间）获取。 实现通常为B-tree和hash两种普遍的数据结构 （下一篇专门讨论）。
        复杂一点，比较常见的查询就是多值（multi-key）和SAM [不知道中文怎么翻。。。] （spatial access method）,比如找一美女我要有年龄，地域，职业，三围的要求等。这时主键索引(primary key indexing) 机制就不能提供效率的改进，所以引进次键索引[不知道是不是这么翻](secondary key)和多键索引(multi-key indexing)的概念。
       再进一步就是 范围查询(range query)和 NN query (nearest neighbor query)。 或着相似度查询(similar search)。 例子就像是查询的对象身材要象林志玲是条件之一。在数据结构端的实现结构或许就是保存所有的三围数据在数据库里，然后通过n-n 查询来获取最近的点。
         最后就是文本配对（Text match 比如我要找性格像赵敏的美女，那数据库应该保存对不同女生性格的文字表述，通过NLP  来进行文本关键字查询）， 图像语音查询（气质像林青霞，长相像赵雅芝，说话不能像林志玲）等。
        对稍复杂一点的查询， b-tree还可以应付，比如通过reverted lists, post-lists 来实现多值查询，但同时split和 merge 的代价都很高。 所以quad-trees, k-d trees, z-ording, R-trees , grid,metric trees 等一些花里胡哨的数据结构开始登场。