所以，BD的目标有两个：
- 如何减少 像顺序扫描那样访问大量的无用的数据（在低选择率的情况下）
- 如何减少 像索引扫描那样，带来的大量随机内存访问（在高选择率的情况下）
- 如何适用于所有的选择率场景？
背景知识
- 本文的Binning是指将多个属性值划分到不想交的多个范围当中，然后使用是一个bit vetcor（bit map→0-1组成的数组）来代表每个范围。值在这个范围内的标为1，不在则标为0 。
BinDex overview
本文介绍一下Bindex的结构：
1. BinDex的数据结构
virtual value space：注意这只是一个虚拟的结构，并没有真正存放在内存中（构建完之后就丢弃了）。其中存放的是按升序排好的N个元素。在原来的base data数据列中仍然是没有顺序的。
virtual areas：根据virtual value space中的元素划分为K个分区，每个分区包含N/K个排好序的元素。如这里的A1，A2。。每个Ai都包含4个值。每个Ai都作为一个bin，后续会用到。
基于上述两个虚拟的结构，设有K个Virtual area（k个bin），在BD中存在三个主要数据结构：Area Map，a set of filter bit vector，Position Array。如上图
Area Map：map S = {S1,S2,S3..Sk-1}，Si对应着Ai+1，如这里的S1对应着A2。每个Si包含（value，count）这样一对值，如其中Si.value表示对应的Ai+1的第一个起始位置的值，Si.count表示Ai+1之前(A1到Ai)有多少个元素。如这里的S1包含（54，4），则54表示A2的第一个元素值为54，A2之前(A1)有个4个元素。若常量c满足，Si-1.value ≤ c < Si.value，则c落在Ai这个区间上。后面会经常用到这个结论来定位区间。
Filter Layer：第一层由a set of filter bit vector一组bit的vector组成，这些vector用于生成扫描的大概结果。基于k个virtual areas，生成k-1的filter bit vector {F1,F2...Fk-1}。即F1→A1,F2→A2...。如F1表示值落在A1中的结果（0≤x<52），对应的位置下标（在position array中）在F1中相应的位置设置为1。最终会生成K-1个bit vector，则进行谓词评估时，选择最接近结果的一个候选的vector（后面推导公式），这个vector中只有一小部分的值需要进行矫正。
Refine Layer：第二层是由Position Array组成。Position Array是基于上面提到的virtual value space中排好序的值的下标组成。该层的作用是将第一层生成的bit vector中某些需要矫正的值进行矫正，以生成最终的结果。矫正流程是这样的，首先通过对Area Map进行二分查找，定位到需要矫正的某个Virtual Area（即分区范围）。然后通过某个Virtual Area对应的Position Array一部分进行二分查找，取出Position Array中的下标，然后根据该下标在（Base Data）原来的数据列取出下标对应的值进行比较，找出需要矫正的值的下标（也即在bit vector中0-1的位置）。
