一种面向微博实时搜索的自适应索引方法

摘要

本发明公开了一种面向微博实时搜索的自适应索引方法，该方法包括：新建大小为π

说明书

技术领域

本发明属于信息技术领域，更具体地，涉及一种面向微博实时搜索的 自适应索引方法。

背景技术

微博实时搜索对微博信息进行即时而快速的搜索，相比传统网页搜索， 微博实时搜索需要索引方法具备低延时、高插入率、实时数据可用性以及 高查询效率的特点；现有的实时索引方法主要包括Earlybird、推文索引 (Tweet Index，TI)和日志结构倒排索引(Log-Structured Inverted Indices， LSII)。Earlybird采取了一种直接将单个倒排索引结构切分成多段较小的独 立倒排索引结构的方法；TI采取了一种只索引热门微博的部分索引方法； LSII提出了一种日志结构的倒排索引结构。相比Earlybird和TI，LSII解决 了索引碎片和查询精度低下的问题；但由于缺乏合适的索引合并策略，LSII 带来了较大的合并开销，造成了查询性能的下降。

目前应用在微博实时索引结构中的合并策略主要包括周期合并、直接 合并和懒惰合并。TI采取周期合并来提高微博更新的效率，LSII采取直接 合并策略维持适量的倒排索引数量，Mercury采取懒惰合并策略来回收空的 索引。由于微博系统的运行环境时刻在变化(主要体现在微博系统每秒接 收到的新微博数量和查询请求的变化)，对于给定的索引结构，高的查询请 求到达速率会带来系统查询资源的匮乏，导致较大的查询请求排队延迟； 相反，低的查询请求到达速率会导致查询资源处于空闲状态，造成查询资 源利用率低下的问题。为了提高动态环境下微博系统的查询性能和稳定性， 索引结构需要自适应的策略来合理利用系统的查询资源。

发明内容

针对现有技术的以上缺陷或改进需求，本发明提供了一种面向微博实 时搜索的自适应索引方法，其目的在于减少索引合并开销并合理利用系统 的查询资源，由此解决现有索引方法查询效率不高、无法适应外部动态环 境的问题。

为实现上述目的，按照本发明的一个方面，提供了一种面向微博实时 搜索的自适应索引方法，具体如下：

(1)判断是否已创建第0层倒排索引i₀，若是，则进入步骤(3)；若 否，则创建一个空间大小为π₀的第0层倒排索引i₀，进入步骤(2)；

(2)将新的微博索引到第0层倒排索引i₀；

(3)判断第0层倒排索引i₀里的微博数量是否达到π₀，若是，则生成 第0层倒排索引i₀的副本即第0层副本i₀`，并将第0层倒排索引i₀清空， 将上述新的微博插入到清空后的第0层倒排索引i₀，进入步骤(4)；若否， 则进入步骤(2)；

(4)判断是否已创建第k层索引包j_k，若是，则进入步骤(6)；若否， 则创建一个空间大小为r^k×π₀的第k层索引包j_k，进入步骤(5)；其中，索 引包为一种能存放多个倒排索引的数据结构；其中，k＝1…m，m是索引结 构的总层数；其中，r是指索引包可容纳的倒排索引数量的最大值，r＝2～ 20。

(5)将第k-1层副本i_k-1`移动到第k层索引包j_k；

(6)判断第k层索引包j_k索引里的微博数量是否达到r^k×π₀，若是，进 入步骤(7)；若否，则进入步骤(5)；

(7)批量合并第k层索引包j_k中的所有倒排索引，获取第k层副本i_k`， 进入步骤(8)；

(8)将第k层索引包j_k清空，并将第k层副本i_k`移动到清空后的第k 层索引包j_k，进入步骤(9)；

(9)k＝k+1，判断加1后的k是否大于p，若是，则进入步骤(10)； 若否，则进入步骤(4)；其中，p是指索引结构可容纳的索引包数量的最大 值；

(10)判断是否已创建第k层倒排索引i_k，若是，则进入步骤(11)； 若否，则将第k层倒排索引i_k的指针指向第k-1层副本i_k-1`，并设置第k层 倒排索引i_k的空间大小为r^k×π₀；

(11)判断第k层倒排索引i_k索引里的微博数量是否达到r^k×π₀，若是， 将第k层副本i_k`的指针指向第k层倒排索引i<sub>k</sub>，将第k层倒排索引i<sub>k</sub>的指 针指向第k-1层副本i<sub>k-1</sub>`，进入步骤(13)；若否，进入步骤(12)；

(12)将第k-1层副本i_k-1`与第k层倒排索引i_k直接合并到第k层倒排 索引i_k；

(13)判断k是否等于m，若是，则将第k层副本i_k`存放到硬盘；若 否，则k＝k+1，并进入步骤(10)。

优选地，步骤(2)包含以下子步骤：

(2-1)对新的微博进行分词处理，形成二元组(t_x,d)，具体为：[(t₁,d), (t₂,d),……(t_x,d)……(t_n,d)]；其中，第x个单词t_x表示微博经过分词处理 后所包含全部单词中第x个单词的id，d表示微博的id；x＝1…n，n表示微 博经过分词处理后所包含单词的数量；

(2-2)针对每个单词t_x，找到第0层倒排索引i₀中t_x指向的倒排表， 将d插入到该倒排表首位；其中，倒排表表示倒排索引中用于存放微博id 的链表结构；对新的微博完成索引。

优选地，步骤(5)包含以下子步骤：

(5-1)判断k是否为1，若是，则进入子步骤(5-2)；若否，则将第 k-1层副本i_k-1`移动到第k层索引包j_k的空闲空间；

(5-2)扫描第k-1层副本i_k-1`，获取全部单词id，进入子步骤(5-3)；

(5-3)针对每个单词id，获取单词id指向的倒排表并将倒排表由原本 的链表结构转换为固定数组结构；处理完成后，进入子步骤(5-4)；该子步 骤中将倒排表的结构由链表转换为适合查询的固定数组结构，可以有效提 高索引的查询性能；

(5-4)将第k-1层副本i_k-1`移动到第k层索引包j_k的空闲空间。

优选的，步骤(7)包含以下子步骤：

(7-1)创建空的第k层副本i_k`；

(7-2)对第k层索引包j_k包含的r个倒排索引进行扫描，获取倒排索 引包含的全部单词id；

(7-3)针对每个单词id，对第k层索引包j_k包含的r个倒排索引进行 扫描，获取该单词id指向的r个倒排表，并将r个倒排表进行首尾合并， 合并的结果存到第k层副本i_k`中该单词id指向的倒排表中；处理完成后， 获取批量合并完成后的第k层副本i<sub>k</sub>`

其中，子步骤(7-2)与(7-3)采取批量合并的方法，能有效降低索引 合并的开销，提高查询的性能。

优选的，步骤(12)包含以下子步骤：

(12-1)扫描第k-1层副本i_k-1`，获取其包含的全部单词id；

(12-2)针对每个单词id，获取该单词id指向的倒排表，并将倒排表 合并到第k层倒排索引i_k中该单词id的倒排表中；处理完成后，获取直接 合并完成后的第k层倒排索引i_k；

其中，步骤(12-1)与(12-2)采取直接合并的策略，可以控制倒排索 引的总体数量以及查询资源的使用情况，且避免了当倒排索引较大时采用 批量合并策略造成的资源利用不当的情况。

优选的，在步骤(13)之后还包括以下步骤：

(14)对每秒钟到达的用户查询请求数量进行监测，实时获取用户查 询请求的到达速率；

(15)根据用户查询请求到达速率的变化情况对索引结构进行自适应 的调整，具体包含以下子步骤；

(15-1)判断用户查询请求到达速率是否上升，若是，则减小p值，进 入步骤(15-2)；若否，则增大p值，进入步骤(15-3)；

(15-2)将处于变化前p值与变化后p值间的索引包包含的倒排索引批 量合并，获取合并后的倒排索引；

(15-3)将处于变化前p值与变化后p值间的倒排索引等量切分成r个 较小的倒排索引，并将该r个倒排索引组成为新的索引包。

上述步骤(15)，根据查询请求到达速率的变化情况，改变p值来调节索 引结构，可自适应地调节查询资源的使用情况，提高动态环境下索引结构 的稳定性。

总体而言，通过本发明所构思的以上技术方案与现有技术相比，能够 取得下列有益效果：

(1)本发明提供的面向微博实时搜索的自适应索引方法中，将倒排表 的结构由链表转换为适合查询的固定数组结构，可以有效提高索引的查询 性能；

(2)本发明提供的面向微博实时搜索的自适应索引方法中，采取批量 合并的策略，能有效降低索引合并的开销，提高查询的性能；

(3)本发明提供的面向微博实时搜索的自适应索引方法中，还采取了 直接合并的策略，可以控制倒排索引的总体数量以及查询资源的使用情况， 且避免了当倒排索引较大时采用批量合并策略造成的资源利用不当的情 况；

(4)本发明提供的面向微博实时搜索的自适应索引方法中，结合了批 量索引策略与直接索引策略，相比单纯采用直接索引策略降低了索引合并 的开销，提高了查询的效率；

(5)发明提供的面向微博实时搜索的自适应索引方法的优选方案里， 通过实时监测外部查询请求的到达速率，根据查询请求到达速率的变化情 况，通过改变阈值来调节索引结构；自适应地调节索引结构以合理利用查 询资源，提高系统在动态外部环境下的稳定性。

附图说明

图1是本发明实施例1提供的面向微博实时搜索的自适应索引方法的 索引结构；

图2为本发明实施例1提供的面向微博实时搜索的自适应索引方法的 流程图；

图3为本发明实施例1提供的面向微博实时搜索的自适应索引方法中 步骤(5)的细化流程图；

图4为本发明实施例1提供的面向微博实时搜索的自适应索引方法中 步骤(7)的细化流程图；

图5为本发明实施例1提供的面向微博实时搜索的自适应索引方法中 步骤(12)的细化流程图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图 及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体 实施例仅仅用以解释本发明，并不用于限定本发明。此外，下面所描述的 本发明各个实施方式中所涉及到的技术特征只要彼此之间未构成冲突就可 以相互组合。

本发明面向微博实时搜索的自适应索引方法的整体索引结构如图1所 示：索引结构由一个大小呈指数增长的索引包与倒排索引序列i₁、j₁、… i_p、j_p、i_p+1、…i_m组成；采用i₀，i_p+1…i_m表示倒排索引，采用j₁…j_p表示索引 包。

本发明实施例1提供的面向微博实时搜索的自适应索引方法，基于图1 所示意的索引结构，处理流程如图2所示，具体包括以下步骤：

(1)判断第0层倒排索引i₀是否已创建，若是，则进入步骤(3)；若 否，则创建一个空间大小为100000的第0层倒排索引i₀，进入步骤(2)；

(2)将新的微博索引到第0层倒排索引i₀，本步骤包含以下子步骤：

(2-1)对微博进行分词处理，形成二元组(t_x,d)，具体为：[(1,56),(2, 56),(3,56)…(9,56)]；

(2-2)针对第x个单词t_x，找到第0层倒排索引i₀中t_x指向的倒排表， 将56插入到该倒排表首位；处理完成后，完成新的微博的索引；

(3)判断第0层倒排索引i₀索引的微博数量是否达到100000，若是， 则生成第0层倒排索引i₀的副本第0层副本i₀`并将第0层倒排索引i₀的微 博清空，将微博插入到清空后的第0层倒排索引i₀，令k＝1，进入步骤 (4)；若否，则进入步骤(2)；其中，k＝1…20；

(4)判断第k层索引包j_k是否已创建，若是，则进入步骤(6)；若否， 则创建一个空间大小为3^k×100000的第k层索引包j_k，进入步骤(5)；在本 实施例里，r为3；

(5)将第k-1层副本i_k-1`移动到第k层索引包j_k；如图3所示，本步 骤包含以下子步骤：

(5-1)判断k是否为1，若是，则进入子步骤(5-2)；若否，则将第 k-1层副本i_k-1`移动到第k层索引包j_k的空闲空间；

(5-2)扫描第0层副本i₀`，获取全部单词id，进入子步骤(5-3)；

(5-3)针对每个单词id，获取单词id指向的倒排表并将倒排表由原本 的链表结构转换为固定数组结构；处理完成后，进入子步骤(5-4)；

(5-4)将第0层副本i₀`移动到第1层索引包j₁的空闲空间；

(6)判断第k层索引包j_k索引的微博数量是否达到3^k×100000，若是， 进入步骤(7)；若否，则进入步骤(5)；

(7)对第k层索引包j_k中的所有倒排索引采取批量合并的策略，批量 合并后得到为第k层副本i_k`，进入步骤(8)，如图4所示，本步骤包含以 下子步骤：

(7-1)创建空的第k层副本i_k`；

(7-2)对第k层索引包j_k包含的3个倒排索引进行扫描，获取倒排索 引包含的全部单词id；

(7-3)针对每个单词id，对第k层索引包j_k包含的3个倒排索引进行 扫描，获取该单词id指向的3个倒排表，并将3个倒排表进行首尾合并， 合并的结果存到第k层副本i_k`中该单词id指向的倒排表中；完成后，获得 批量合并完成后的第k层副本i<sub>k</sub>`。

子步骤(7-2)与(7-3)采取批量合并的策略，减少了合并开销，在当 前实例中降低了大约8％的查询时间；

(8)将第k层索引包j_k清空，并将第k层副本i_k`移动到清空后的第k 层索引包j_k，进入步骤(9)；

(9)k＝k+1，判断k是否大于2，若是，则进入步骤(10)；若否，则 进入步骤(4)；

(10)判断第k层倒排索引i_k是否已创建，若是，则进入步骤(11)； 若否，则将第k层倒排索引i_k的指针指向第k-1层副本i_k-1`，并将第k层倒 排索引i_k的空间大小设为3^k×100000；

(11)判断第k层倒排索引i_k索引的微博数量是否达到3^k×100000，若 是，将第k层副本i_k`的指针指向第k层倒排索引i<sub>k</sub>，将第k层倒排索引i<sub>k</sub>的指针指向第k-1层副本i<sub>k-1</sub>`，进入步骤(13)；若否，进入步骤(12)；

(12)将第k-1层副本i_k-1`与第k层倒排索引i_k直接合并到第k层倒排 索引i_k，本步骤包含以下子步骤：

(12-1)扫描第k-1层副本i_k-1`，获取其包含的全部单词id；

(12-2)针对每个单词id，获取该单词id指向的倒排表，并将倒排表 合并到第k层倒排索引i_k中该单词id的倒排表中；获取直接合并完成后的 第k层倒排索引i_k；

(13)判断k＝＝20是否成立，若是，则将第20层副本i₂₀`存放到硬盘； 若否，则k＝k+1，并进入步骤(10)；

(14)对每秒钟到达的用户查询请求数量进行监测，实时获取用户查 询请求的到达速率；

(15)根据用户查询请求到达速率的变化情况对索引结构进行自适应 的调整，具体包含以下子步骤；

(15-1)当查询请求的到达速率低于3200条/s时，p值保持10不变； 当超过3200/s时，该速率每提升20％-30％，p值减小1，直至减小到0，反 之亦然。判断p值是否变化，若减小，则进入子步骤(15-2)；若增大，则 进入子步骤(15-3)；若无变化，则继续周期性地监测p值的变化；

(15-2)将处于变化前p值与变化后p值间的索引包包含的倒排索引批 量合并，获取合并后的倒排索引；

(15-3)将处于变化前p值与变化后p值间的倒排索引等量切分成3 个较小的倒排索引，并将该3个倒排索引组成为新的索引包。

在当前实例中，p初值设为2，索引结构中前两层索引包采取批量合并 策略，后面层倒排索引采取直接合并策略。由于批量合并能够降低索引合 并的开销，结合了批量合并策略与直接合并策略的自适应合并策略相比原 本的直接合并策略，最终在查询时间上降低了大约8％。

本领域的技术人员容易理解，以上所述仅为本发明的较佳实施例而已， 并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等 同替换和改进等，均应包含在本发明的保护范围之内。