搜索引擎

image.png

搜索数据的存储该怎么设计呢？

• 倒排索引 (Inverted Index)

• “倒排”，指的是存储的结构不再是先定位到文章，再去文章的内容中找寻关键字了；而是反过来，先定位到关键字，再去看关键字属于哪些文章。

• “索引”，指的是关键字，是被索引起来的，因此查询的速度会比较快。

1. 添加一个关键字表 KEYWORDS，并且，KEYWORD 列需要添加索引，因此这条关键字的记录可以被迅速找到：

image.png

2. 一个关联关系表把 KEYWORDS 表和 ARTICLES 表结合起来，KEYWORD_ID 和 ARTICLE_ID 作为联合主键：

image.png

3. 这其实是一个多对多的关系，即同一个关键字可以出现在多篇文章中，而一篇文章可以包含多个不同的关键字。

这个方法只解决了全表扫描和字符串 % 匹配查询造成的性能问题，并且，在数据量较大时，并没有解决数据量本身在单机模式下造成的性能问题。

Elasticsearch 将关键字使用哈希算法分散到多个不同的被称为“Shard”的虚拟节点，并且把它们部署到不同的机器节点上，且每一个 shard 具备指定数量的冗余副本（Replica），这些副本要求被放置到不同的物理机器节点上。通过这样的方式，我们就可以保证每台机器都只管理稳定且可控的数据量，并且保证了搜索服务数据的可用性。

image.png

例子:

对于每一个关键字，都可以配置指向文章和文章中位置的映射。比如有这样两篇文章：

• 文章 1 的正文是：今天介绍存储技术。
• 文章 2 的正文是：存储技术有多种分类。

那么，就有如下映射关系（下表仅用于表示在 Shard 中的数据映射，并非关系数据库表）：

image.png

DOCUMENT 这一部分，每一行都可以存放若干个“文章 id : 文中关键字的位置”的组合。

地理信息系统

每个饭馆的位置可以简单考虑为经度和纬度组合的坐标.

image.png

1. 把这样的地理信息，放到一张 LOCATIONS 表上，就会是这样：

image.png

2. RESTAURANTS 表：

image.png

3. 要查出范围内的饭馆，我们就可以写这样的 SQL：

<pre class="cm-s-default" style="color: rgb(89, 89, 89); margin: 0px; padding: 0px; background: none 0% 0% / auto repeat scroll padding-box border-box rgba(0, 0, 0, 0);">select * from LOCATIONS l, RESTAURANTS r where l.RESTAURANT_ID = r.RESTAURANT_ID and l.LONGITUDE >= 经度下界 and l.LONGITUDE <= 经度上界 and l.LATITUDE >= 纬度下界 and l.LATITUDE <= 纬度上界;</pre>

4. 这个经度、纬度的上下界，是根据用户所在位置，以及地图缩放程度折算出来的。显然，这需要一个全表扫描，加一个笛卡尔积，复杂度偏高

优化

思路 1：给单一维度加索引

如果经纬度可以分开处理.

1. 只考虑经度的话，给经度一列建立索引，所有饭馆按照从小到大的顺序排好。这样的话，当给定范围的时候，我们就可以快速找到经度范围内所有满足经度条件的饭馆。
2. 从时间复杂度的角度来考虑，在不做额外优化的情况下，以在有序经度列上的二分查找为例，这个复杂度是 log(n)。
3. 当再考虑纬度的时候，假如有 m 家满足经度条件的饭馆，接下去我们就只能挨个去检查这 m 家饭馆，找出它们中满足纬度条件的了，也就是说，总的时间复杂度是 m*log(n)。这种方法比较简单，在数据量不太大的情况下也没有太大问题，因此这已经是很好的方法了。但是，在某些场景下这个 m 还有可能比较大

思路 2：GeoHash

1. GeoHash，它的大致思路就是降维。即把一个经度和纬度的二维坐标用一个一维的数来表示。具体实现上，有一种常见的办法就是把经度和纬度用一个长位数的数来表示，比如：

<pre class="cm-s-default" style="color: rgb(89, 89, 89); margin: 0px; padding: 0px; background: none 0% 0% / auto repeat scroll padding-box border-box rgba(0, 0, 0, 0);">经度：101010…… 纬度：100110……</pre>

2. 接着把二者从左到右挨个位拼接，黑色字符来自经度，蓝色字符来自纬度：

image.png

在这种方式下，从结果的左边最高位开始，取任意长度截断所得到的前缀，可以用来匹配距离目标位置一定距离范围的所有饭馆。当用户选取的地图范围越大，前缀长度就越长，这个匹配精度也就越高，匹配到的饭馆数量也就越少。通过这种方式，区域不断用前缀的方式来细分，相当于给每个子区域一个标记号码。

3. 我们数据库表中的经度和纬度就可以合并为一列，再令这一列为主键，或者做索引，就能够进行单列的范围查询了。

image.png

SQL or NoSQL？

两个前提角度

数据分类:

1. 商品元数据，即商品的描述、厂家等等信息；
2. 媒体数据，比如图片和视频；
3. 库存数据，包括在某个地点的库房某商品还有多少件库存；
4. 交易信息，比如订单、支付、余额管理；
5. 用户信息，涉及的功能包括登陆、注册和用户设置。

数据规模:

• 可大可小

选择的思路

• 对于中小型系统，在数据量不大且没有特殊的吞吐量、可用性等要求的情况下，或者在多种关系和非关系数据库都满足业务要求的情况下，优先考虑关系数据库。

• 较强的扩展能力

• 不要觉得 NoSQL 是大数据量的一个必然选择

• Sharding 和 Partitioning 技术

• 数据可用性的问题，也可以使用集群加冗余技术来解决 (牺牲一致性)

• 是否具备明确的 schema 定义，是否需要支持关系查询和事务？如果有一项回答“是”，优先考虑关系数据库。

• 如果符合结构不定（包括半结构化和无结构化）、高伸缩性、最终一致性、高性能（高吞吐量、高可用性、低时延等）的特点和要求，可以考虑非关系数据库。

总结与思考

设计持久层，都有哪些需要考虑的方面呢？

代码层面:

• 提供数据服务的设计，即 MVC 中模型层的设计, 08讲
• 对于模型到关系数据库的映射（ORM）和技术选择, 12讲加餐

系统层面:

• 持久层内部或者持久层之上的缓存技术, 21, 22讲
• 对于持久化的核心关注点之一 ——一致性，包括存储系统扩容的基础技术一致性哈希, 23讲
• 关于分布式数据存储涉及到的 CAP 理论和应用，以及相关的 ACID、BASE 原则, 24讲
• 持久层存储技术的选择, 25讲

公众号：码农架构