机器学习如何影响系统设计
发布时间：2021-04-18 16:30:11 所属栏目：动态 来源：互联网
导读：根据济南站长网 Www.0531Zz.Com报道 ndex（索引）是数据库、文件系统等领域常见的数据结构，最经典的莫过于B-Tree。B-Tree是一种范围索引（Range Index）数据结构，查询时给定一个key（或一些确定范围的keys），B-Tree会索引到包含该key的对应范围的叶子节点
|
根据济南站长网 Www.0531Zz.Com报道 ndex（索引）是数据库、文件系统等领域常见的数据结构，最经典的莫过于B-Tree。B-Tree是一种范围索引（Range Index）数据结构，查询时给定一个key（或一些确定范围的keys），B-Tree会索引到包含该key的对应范围的叶子节点，在叶子节点内对key进行搜索。如果该key在索引中存在，就会得到其对应的位置。一般在一个逻辑页内的记录会用一个key来索引。如图1（a）所示，输入是一个key，输出是对应要查询记录的位置区间。除了范围索引，还有点索引（Point Index）如：哈希表（Hash Map），和存在索引（Existence Index）如：Bloom Filters，也都是常用的索引数据结构。Learned Index Structures的主要思想是将这里B-Tree或是Bloom Filters等数据结构替换为机器学习的模型——查找操作变成了根据key做索引数据位置的预测，如图1（b）所示。我们以范围索引为例，来详细介绍下Learned Index Structures的设计和实现思路。 1就是一个传统B-tree和Learned Index的对比。可以看到，Learned Index的输入是Key，输出是这个key对应的检索结果的位置（可能有误差），误差的上限是叶子节点一个数据页中的结果条目（即所需检索结果在数据页的末尾）。 那么针对范围索引，如何设计机器学习的模型呢？这里只考虑一维聚簇索引的情况（即数据是按照用于查找的 key来排序的，非聚簇索引可以通过聚簇索引加一层到真实数据排列的指针实现），Learned Index Structures很巧妙的给出了如图2所示的洞察，索引位置实际上是随着Key增长而增长的单调递增函数。虽然具体的索引可能是离散的,整体上还是可以用一个函数来描述： p = F(Key) * N
其中， p是估计得到的位置，N是索引Key的数量，F(key)是索引数据的累计分布函数（CDF）。F（key）的含义是小于等于key的索引数据条目总和（即key的位置估计）。本质上体现了数据集的分布特征。相比B-Tree的通用设计，Learned Index Structures考虑了数据集的内在分布特点并将其用于优化索引的结构。Learned Index误差上限可控，只需要在误差范围内根据预测的位置向左或向右二分查找即可准确找到查找目标。 （编辑：玉林站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
