密匙四、Trie树/数据库/倒排索引

Trie树

  • 适用范围：

    数据量大，重复多，但是数据种类小可以放入内存 基本原理及要点：实现方式，节点孩子的表示方式

  • 扩展：

    压缩实现。

问题实例：

  1. 上面的第2题：寻找热门查询：查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个，每个不超过255字节。

  2. 上面的第5题：有10个文件，每个文件1G，每个文件的每一行都存放的是用户的query，每个文件的query都可能重复。要你按照query的频度排序。

  3. 1000万字符串，其中有些是相同的(重复),需要把重复的全部去掉，保留没有重复的字符串。请问怎么设计和实现？

  4. 上面的第8题：一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词。其解决方法是：用trie树统计每个词出现的次数，时间复杂度是O(n*le)（le表示单词的平准长度），然后是找出出现最频繁的前10个词。

第一部分、Trie树

1.1、什么是Trie树

Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。

Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

它有3个基本性质：

  1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符。

  2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。

  3. 每个节点的所有子节点包含的字符都不相同。

参考文档： http://blog.csdn.net/v_july_v/article/details/6897097

http://www.cnblogs.com/huangxincheng/archive/2012/11/25/2788268.html

数据库索引

  • 适用范围：

    大数据量的增删改查

  • 基本原理及要点：

    利用数据的设计实现方法，对海量数据的增删改查进行处理。

关于数据库索引及其优化，更多可参见此文：
http://www.cnblogs.com/pkuoliver/archive/2011/08/17/mass-data-topic-7-index-and-optimize.html；

关于MySQL索引背后的数据结构及算法原理，这里还有一篇很好的文章： http://blog.codinglabs.org/articles/theory-of-mysql-index.html；

关于B 树、B+ 树、B* 树及R 树，本blog内有篇绝佳文章： http://blog.csdn.net/v_JULY_v/article/details/6530142。