用Golang写一个搜索引擎（0x09）— 数据增，删，改
|
根据某位和我同姓的朋友的建议，后面的文章都会加上副标题，方便查阅。 今天的文章会比较短，很快就能看完。 按照步骤，说完段层以后，应该就开始涉及到索引层了，但我想说的是一个分布式的搜索引擎，所以除了索引层以外，还有个分片层，这两个概念是紧密联系在一起的，我怕说不好，所以在说索引层和分片层之前，我们先直观的对索引有个了解，并且先熟悉一下索引层的一些特殊的数据结构以及一些常用算法，让大家对搜索引擎有个整体了解以后再来说说索引层和分片层。 本篇只会涉及到数据的增，删，改，因为查是一个大的话题，涉及的东西有点多，可能需要单独的一篇甚至两篇来说，好了，不废话，我们来说说今天的主题吧。 之前我们已经基本将搜索引擎的底层数据结构介绍完毕了，那么一个搜索引擎最基本的功能也和数据库一样，为了使搜索引擎跑起来，必须要有增，删，改，查四个基本功能，下来我们一个一个来说。 在这之前，我们还需要一些准备工作，那么还是用一个例子引出所有内容，假如我们有一份这样的微博数据，每一条数据就是一个微博用户发布的一条微博，每条数据有三个字段，分别是用户昵称，微博内容，发布时间，具体数据长成这样子：
那么首先，我们需要建立一个这样的索引结构
好了，把上面这个表的内容提交到搜索引擎中，就建立好这个索引结构了，搜索引擎会按照我们之前所写的，建立好各个字段，给每个字段建立好倒排和正排 增增这个其实就是全量索引构建和增量索引构建了，我们之前一直再说的就是这个，这里我们就不详细说了。 不管是全量还是增量，增加数据的时候就是将一条一条上文中的原始数据导入到搜索引擎中，每增加一条数据会先在内存中增加数据，然后达到一定条件以后将一批数据写入到段文件中，并且达到一定条件以后会将各个段合并起来。 唯一要说的是主键这个字段，由于在原始数据中是没有_id这个东西的，所以在增加数据的时候搜索引擎内部会给每条数据生成一个_id。 具体的_id的生成方法有很多，可以使用随机数生成，也可以使用GUID的方法进行生成，只要保证_id的唯一性就行了，由于最后我们需要的是一个分布式的搜索引擎，所以_id的生成方法还是有一些讲究的，一般简单的可以用随机数-时间戳-本机IP(MAC)地址来生成，这样产生相同的_id概率就已经几乎没有了，当然对于分布式系统还有其他办法生成唯一_id，我们以后会介绍。 主键的倒排我没有保存在段中，而是直接使用了一个叫primary.pk的B+树文件进行保存，这个B+树的value就是主键对应的docid，因为主键是唯一的，所以只需要一个value值就行了，不需要倒排链。 如果数据中自带唯一id，那么更简单，直接使用就行了。 一般搜索引擎也提供无主键的数据检索，这种索引就只有增加和检索操作了，由于没有主键，一般不提供删除和修改操作。 删删除操作是搜索引擎比较特殊的操作，因为我们知道，保存到搜索引擎中的数据有倒排文件，想想倒排文件的数据结构，要从中删除一个文档的话，需要先找出这个文档的内容，然后找到所有包含这个文档的倒排链，然后把每个倒排链中的文档删除掉，再把倒排链从新排列，写入倒排文件中，加上读取词典数据，少说也有6，7次IO。 很麻烦是不是，我们当然不会这么做，这里，我们用到了一个新的数据结构，bitmap，分分钟解决问题。 bitmap是什么？bitmap是一种非常高效和常用的数据结构，它通过一个bit数组来存储特定数据的一种数据结构；由于bit是数据的最小单位，所以这种数据结构往往是非常节省存储空间，而一个bit要不是0，要不是1，所以bitmap只适合用来存储ture/false的这种数据（扩展以后可以存储更多信息），比如下面就是一个32位的bitmap，它可以用来表示0到31这些数中，哪些是有效的（用0表示），哪些是无效的（用1表示），在这里，0，4，14这三个数是无效的。这个数据结构很好理解吧。
而搜索引擎中，docid是连续的，并且docid是有效的还是被删除了正好对应ture和false，所以非常适合使用bitmap来描述某个文档是否被删除。 bitmap的基本运算是位运算，所以速度也特别快，并且bitmap用一个bit来表示一个文档，所以存储空间也非常少，一个16M的bitmap可以存储134217728个文档是否被删除的信息。 所以，在搜索引擎中删除一个数据，我们按照以下几步进行
所以说是删除，实际并没有删除，数据还在，在检索的时候做点小动作就能让人觉得被删除了，什么小动作说检索的时候再说吧。 改有了增和删，改的话就简单了，先删再增就是改了。 改的话还有个小技巧，为了尽量的少增加数据量，当我们修改的时候如果只修改了正排字段，并且修改前后正排字段的长度没有发生变化的话，我们可以直接在原始的记录上覆盖，而不用删除再增加记录，当然，这么做的话，修改的时候需要比对所有字段来判断使用哪种更新模式，不如先删后增来得直接，而且在分布式的环境下，这样不太利于同步数据。 结说完了增，删，改，特别特别简单吧，但我们发现搜索引擎如果一直不停的修改删除数据的话，而实际上并没有真正的删除数据，数据会越来越多并不会减少，所以搜索引擎每隔一段时间都要重做一下全量索引，把无用的数据真正的清除掉，不然冗余的数据越来越多，会影响查询的效率。 后面一篇我们再来详细说说查，涉及到的算法部分稍微多一点，一篇可能说不完。 如果想看其他文章，欢迎关注我的公众号，主要聊聊搜索引擎，推荐广告算法以及其他瞎扯的东西 ：） （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |