数据持久化-数据结构与算法(上)

当前位置:　首页>> 技术小册>> 数据结构与算法(上)

在接下来的几个练习中，我们将返回到网页搜索引擎的构建。为了回顾，搜索引擎的组件是：

+   抓取：我们需要一个程序，可以下载一个网页，解析它，并提取文本和任何其他页面的链接。
+   索引：我们需要一个索引，可以查找检索项并找到包含它的页面。
+   检索：我们需要一种方法，从索引中收集结果，并识别与检索项最相关的页面。

如果你做了练习 8.3，你使用 Java 映射实现了一个索引。在本练习中，我们将重新审视索引器，并创建一个新版本，将结果存储在数据库中。

如果你做了练习 7.4，你创建了一个爬虫，它跟踪它找到的第一个链接。在下一个练习中，我们将制作一个更通用的版本，将其查找到的每个链接存储在队列中，并对其进行排序。

然后，最后，你将处理检索问题。

在这些练习中，我提供较少的起始代码，你将做出更多的设计决策。这些练习也更加开放。我会提出一些最低限度的目标，你应该尝试实现它们，但如果你想挑战自己，有很多方法可以让你更深入。

现在，让我们开始编写一个新版本的索引器。

## 14.1 Redis

索引器的之前版本，将索引存储在两个数据结构中：`TermCounter`将检索词映射为网页上显示的次数，以及`Index`将检索词映射为出现的页面集合。

这些数据结构存储在正在运行的 Java 程序的内存中，这意味着当程序停止运行时，索引会丢失。仅在运行程序的内存中存储的数据称为“易失的”，因为程序结束时会消失。

在创建它的程序结束后，仍然存在的数据称为“持久的”。通常，存储在文件系统中的文件，以及存储在数据库中的数据是持久的。

使数据持久化的一种简单方法是，将其存储在文件中。在程序结束之前，它可以将其数据结构转换为 JSON 格式，然后将它们写入文件。当它再次启动时，它可以读取文件并重建数据结构。

但这个解决方案有几个问题：

+   读取和写入大型数据结构（如 Web 索引）会很慢。
+   整个数据结构可能不适合单个运行程序的内存。
+   如果程序意外结束（例如，由于断电），则自程序上次启动以来所做的任何更改都将丢失。

一个更好的选择是提供持久存储的数据库，并且能够读取和写入数据库的部分，而无需读取和写入整个数据。

有多种数据库管理系统（DBMS）提供不同的功能。

我为这个练习推荐的数据库是 Redis，它提供了类似于 Java 数据结构的持久数据结构。具体来说，它提供：

字符串列表，与 Java 的`List`类似。
哈希，类似于 Java 的`Map`。
字符串集合，类似于 Java 的`Set`。

> 译者注：另外还有类似于 Java 的`LinkedHashSet`的有序集合。

Redis 是一个“键值数据库”，这意味着它包含的数据结构（值）由唯一的字符串（键）标识。Redis 中的键与 Java 中的引用相同：它标识一个对象。我们稍后会看到一些例子。

## 14.2 Redis 数据类型

Redis 基本上是一个从键到值的映射，键是字符串，值可以是字符串，也可以是几种数据类型之一。最基本的 Redis 数据类型是字符串。我将用斜体书写 Redis 类型，来区别于 Java 类型。

为了向数据库添加一个字符串，请使用`jedis.set`，类似于`Map.put`; 参数是新的键和相应的值。为了查找一个键并获取其值，请使用`jedis.get`：

```java
        jedis.set("mykey", "myvalue");
        String value = jedis.get("mykey");
```

在这个例子中，键是`"mykey"`，值是`"myvalue"`。

Redis 提供了一个集合结构，类似于 Java 的`Set<String>`。为了向 Redis 集合添加元素，你可以选择一个键来标识集合，然后使用`jedis.sadd`：

```java
        jedis.sadd("myset", "element1", "element2", "element3");
        boolean flag = jedis.sismember("myset", "element2");
```

你不必用单独的步骤来创建集合。如果不存在，Redis 会创建它。在这种情况下，它会创建一个名为`myset`的集合，包含三个元素。

`jedis.sismember`方法检查元素是否在一个集合中。添加元素和检查成员是常数时间的操作。

Redis 还提供了一个列表结构，类似于 Java 的`List<String>`。`jedis.rpush`方法在末尾（右端）向列表添加元素：

```java
        jedis.rpush("mylist", "element1", "element2", "element3");
        String element = jedis.lindex("mylist", 1);
```

同样，你不必在开始添加元素之前创建结构。此示例创建了一个名为`mylist`的列表，其中包含三个元素。

`jedis.lindex`方法使用整数索引，并返回列表中指定的元素。添加和访问元素是常数时间的操作。

最后，Redis 提供了一个哈希结构，类似于 Java 的`Map<String, String>`。`jedis.hset`方法为哈希表添加新条目：

```java
        jedis.hset("myhash", "word1", Integer.toString(2));
        String value = jedis.hget("myhash", "word1");
```

此示例创建一个名为的`myhash`哈希表，其中包含一个条目，该条目从将键`word1`映射到值`"2"`。

键和值都是字符串，所以如果我们要存储`Integer`，在我们调用`hset`之前，我们必须将它转换为`String`。当我们使用`hget`查找值时，结果是`String`，所以我们可能必须将其转换回`Integer`。

使用 Redis 的哈希表可能会令人困惑，因为我们使用一个键来标识我们想要的哈希表，然后用另一个键标识哈希表中的值。在 Redis 的上下文中，第二个键被称为“字段”，这可能有助于保持清晰。所以类似`myhash`的“键”标志一个特定的哈希表，然后类似`word1`的“字段”标识一个哈希表中的值。

对于许多应用程序，Redis 哈希表中的值是整数，所以 Redis 提供了一些特殊的方法，比如`hincrby`将值作为数字来处理：

```java
        jedis.hincrBy("myhash", "word2", 1);
```

这个方法访问`myhash`，获取`word2`的当前值（如果不存在则为`0`），将其递增`1`，并将结果写回哈希表。

在哈希表中，设置，获取和递增条目是常数时间的操作。

## 14.3 练习 11

这个时候，你可以获取一些信息，你需要使用它们来创建搜索引擎的索引，它将结果储存在 Redis 数据库中。

现在运行`ant JedisIndexTest`。它应该失败，因为你有一些工作要做！

`JedisIndexTest`测试了这些方法：

+   `JedisIndex`，这是构造器，它接受`Jedis`对象作为参数。
+   `indexPage`，它将一个网页添加到索引中；它需要一个`StringURL`和一个`jsoup Elements`对象，该对象包含应该建立索引的页面元素。
+   `getCounts`，它接收检索词，并返回`Map<String, Integer>`，包含检索词到它在页面上的出现次数的映射。

以下是如何使用这些方法的示例：

```java
        WikiFetcher wf = new WikiFetcher();
        String url1 = 
            "http://en.wikipedia.org/wiki/Java_(programming_language)";
        Elements paragraphs = wf.readWikipedia(url1);

Jedis jedis = JedisMaker.make();
        JedisIndex index = new JedisIndex(jedis);
        index.indexPage(url1, paragraphs);
        Map<String, Integer> map = index.getCounts("the");
```

如果我们在结果`map`中查看`url1`，我们应该得到`339`，这是 Java 维基百科页面（即我们保存的版本）中，`the`出现的次数。

如果我们再次索引相同的页面，新的结果将替换旧的结果。

将数据结构从 Java 翻译成 Redis 的一个建议是：记住 Redis 数据库中的每个对象都以唯一的键标识，它是一个字符串。如果同一数据库中有两种对象，则可能需要向键添加前缀来区分它们。例如，在我们的解决方案中，我们有两种对象：

+   我们将`URLSet`定义为 Redis 集合，它包含`URL`，`URL`又包含给定检索词。每个`URLSet`的键的起始是`"URLSet:"`，所以要获取包含单词`the`的 URL，我们使用键`"URLSet:the"`来访问该集合。
+   我们将`TermCounter`定义为 Redis 哈希表，将出现在页面上的每个检索词映射到它的出现次数。`TermCounter`每个键的开头都以`"TermCounter:"`开头，以我们正在查找的页面的 URL 结尾。

在我的实现中，每个检索词都有一个`URLSet`，每个索引页面都有一个`TermCounter`。我提供两个辅助方法，`urlSetKey`和`termCounterKey`来组装这些键。

## 14.4 更多建议（如果你需要的话）

到了这里，你拥有了完成练习所需的所有信息，所以如果准备好了就可以开始了。但是我有几个建议，你可能想先阅读它：

+   对于这个练习，我提供的指导比以前的练习少。你必须做出一些设计决策；特别是，你将必须弄清楚如何将问题分解成，你可以一次性测试的部分，然后将这些部分组合成一个完整的解决方案。如果你尝试一次写出整个项目，而不测试较小的部分，调试可能需要很长时间。
+   使用持久性数据的挑战之一是它是持久的。存储在数据库中的结构可能会在每次运行程序时发生更改。如果你弄乱了数据库，你将不得不修复它或重新开始，然后才能继续。为了帮助你控制住自己，我提供的方法叫`deleteURLSets`，`deleteTermCounters`和`deleteAllKeys`，你可以用它来清理数据库，并重新开始。你也可以使用`printIndex`来打印索引的内容。
+   每次调用 Jedis 的方法时，你的客户端会向服务器发送一条消息，然后服务器执行你请求的操作并发回消息。如果执行许多小操作，可能需要很长时间。你可以通过将一系列操作分组为一个`Transaction`，来提高性能。

例如，这是一个简单的`deleteAllKeys`版本：

```java
    public void deleteAllKeys() {
        Set<String> keys = jedis.keys("*");
        for (String key: keys) {
            jedis.del(key);
        }
    }
```

每次调用`del`时，都需要从客户端到服务器的双向通信。如果索引包含多个页面，则该方法需要很长时间来执行。我们可以使用`Transaction`对象来加速：

```java
    public void deleteAllKeys() {
        Set<String> keys = jedis.keys("*");
        Transaction t = jedis.multi();
        for (String key: keys) {
            t.del(key);
        }
        t.exec();
    }
```

`jedis.multi`返回一个`Transaction`对象，它提供`Jedis`对象的所有方法。但是当你调用`Transaction`的方法时，它不会立即执行该操作，并且不与服务器通信。在你调用`exec`之前，它会保存一批操作。然后它将所有保存的操作同时发送到服务器，这通常要快得多。

## 14.5 几个设计提示

现在你真的拥有了你需要的所有信息；你应该开始完成练习。但是如果你卡住了，或者如果你真的不知道如何开始，你可以再来一些提示。

在运行测试代码之前，不要阅读以下内容，尝试一些基本的 Redis 命令，并在`JedisIndex.java`中编写几个方法。

好的，如果你真的卡住了，这里有一些你可能想要处理的方法：

```java
    /**
     * 向检索词相关的集合中添加 URL
     */
    public void add(String term, TermCounter tc) {}

/**
     * 查找检索词并返回 URL 集合
     */
    public Set<String> getURLs(String term) {}

/**
     * 返回检索词出现在给定 URL 中的次数
     */
    public Integer getCount(String url, String term) {}

/**
     * 将 TermCounter 的内容存入 Redis
     */
    public List<Object> pushTermCounterToRedis(TermCounter tc) {}
```

这些是我在解决方案中使用的方法，但它们绝对不是将项目分解的唯一方法。所以如果他们有帮助，请接受这些建议，但是如果没有，请忽略它们。

对于每种方法，请考虑首先编写测试。当你弄清楚如何测试一个方法时，你经常会了解如何编写它。

祝你好运！

该分类下的相关小册推荐：

业务开发实用算法精讲

编程之道-算法面试(下)

编程之道-算法面试(上)

数据结构与算法(下)

算法面试通关 50 讲

数据结构与算法之美

数据结构与算法(中)