数据库查询的索引原理介绍 (面试必问)_数据库查询原理

数据库查询的索引原理介绍 (面试必问)

目录

1.一个属性的查询
· 线性扫描
· 二分查找
· Hashing
· B-Tree
2.多个属性的查询
· Bitmap!
· MA.Hashing
· Grid Files
· kd-Trees
· Quad Trees

一个属性的查询

通俗的说，就是 select 语句后边，只对一个属性进行过滤，例如:

select * from Employees where id = 15567;
select * from Employees where age = 25;
select * from Employees where age>20 and age<50;
1
2
3

常用的算法如下:

线性扫描

因为如果 b 条记录是无序的，只能通过线性扫描进行查找.
时间复杂度：最好 O(1), 平均 b/2, 最差 b

题外话 +1: 对于乱序存储，每条记录 (tuple) 直接存在一个文件 (heap file) 中。删除记录：标记删除而不是物理删除。添加记录：在文件的最末端插入一条记录.

二分查找

如果记录是有序存储的话，自然想到可以用 二分查找.

这么做查询虽然起飞了，但插入数据的效率降低了 (每插入一个数据都要重新更新保存所有数据。这个世界就是这样，无论什么都是有 trade off 的).

所以对数据库的有序存储做了一个优化：首先按范围分好区间，每一块代表一个 page (见下图), 当某个区间存满了之后，会链接 (link) 一个新的 Overflow Page 继续存储。因为大部分情况下，都是少量的插入与删除 (Large-scale file re-arrangement occurs less frequently). 最终可以二分查找搜索 page, 再去遍历搜索具体的记录.

时间复杂度：最好 O (1), 最差 Ov * (log2b + bov) (Ov 代表每个 page 记录的大小，bov 代表 Overflow Page 的数量)
题外话 +1: 想起之前面试的一道题: 二分查找搜索范围

Hashing

最简单就是取余。例如有数组 [1, 3, 4, 7, 8, 9], 并假设只有 3 个 page 可以存储，就对每个数字除以 3 取余: [1, 0, 1, 1, 2, 0], 其中每个数字就对应插入和查询的位置 (page0, page1, page2).

B-Trees

太经典了，就不多说了。参考我的另一篇博客: <算法导论 (3rd)> 第十八章 - B Tree!

多个属性的查询

Bitmap!
不多解释了，看图。所以查询颜色为 red, 并且小于 $4 的所有记录，只需要对 100011 和 110001 做与操作就可以了，太酷了.

MA.Hashing(Multi-attribute Hashing)

取多个字段 hash 值的最后一位，组成一个新的 hash. 唯一的缺点是，不像单个字段的 hash, 永远返回的是一个 page, MA.Hashing 会返回多个 pages.

Grid Files

将数据按属性 a 和 b 分成 4*8 的表格，所以:

select...where a=C1 and b=C2: 查询一个单元格 对应的数据.
select...where a=C1: 查询一行 (四个单元格)
select...where b=C2: 查询一列 (八个单元格)
1
2
3

kd-Trees（二叉树）

将下边的两张图联系起来看就明白了，实际上就是对一个二维空间按条件做了划分。查询时也能按条件快速查找.

平衡二叉树

在一棵二叉查找树中插入结点后，调整其为平衡二叉树。若向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性。首先要找出插入新结点后失去平衡的最小子树根结点的指针。然后再调整这个子树中有关结点之间的链接关系，使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后，原有其他所有不平衡子树无需调整，整个二叉排序树就又叫做平衡二叉树。

1.调整方法
（1）插入点位置必须满足二叉查找树的性质，即任意一棵子树的左结点都小于根结点，右结点大于根结点。
（2）找出插入结点后不平衡的最小二叉树进行调整，如果是整个树不平衡，才进行整个树的调整。
2.调整方式
（1）LL型
LL型：插入位置为左子树的左结点，进行向右旋转

由于在A的左孩子B的左子树上插入结点F，使A的平衡因子由1变为2，成为不平衡的最小二叉树根结点。此时A结点顺时针右旋转，旋转过程中遵循“旋转优先”的规则，A结点替换D结点成为B结点的右子树，D结点成为A结点的左孩子。
（2）RR型
RR型：插入位置为右子树的右孩子，进行向左旋转

AVL树中的结点的数据结构可以表示为:

public class AVLNode {

    //节点的值
    public int key;

    //节点的平衡度
    public int balance;

    //分别指向节点的左孩子、右孩子与父节点
    public AVLNode left, right, parent;

    /**
     * @function 默认构造函数
     * @param k
     * @param p
     */
    AVLNode(int k, AVLNode p) {
        key = k;
        parent = p;
    }
}
Rebala
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

磁盘存取原理

索引一般以文件形式存储在磁盘上，索引检索需要磁盘I/O
与主存不同，磁盘I/O存在机械消耗，因此磁盘I/O时间消耗巨大

磁盘由大小相同且同轴的圆形盘片组成，磁盘可以转动（各磁盘必须同步转动）。

在磁盘的一侧有磁头支架，磁头支架固定了一组磁头，每个磁头负责存取一个磁盘的内容。磁头不能转动，但是可以沿磁盘半径方向运动（实际是斜切向运动），每个磁头同一时刻也必须是同轴的，即从正上方向下看，所有磁头任何时候都是重叠的（不过目前已经有多磁头独立技术，可不受此限制）

盘片被划分成一系列同心环，圆心是盘片中心，每个同心环叫做一个磁道，所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段，每个段叫做一个扇区，每个扇区是磁盘的最小存储单元。为了简单起见，我们下面假设磁盘只有一个盘片和一个磁头。

当需要从磁盘读取数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。

为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点，磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间，然后磁盘旋转将目标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间。

B*tree 的结构

B树定义了非叶子结点关键字个数至少为（2/3) M,即块的最低使用率为2/3(代替B+树的1/2)。
B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新节点，最后在父亲结点中增加新节点的指针；B+树的分裂只影响原结点和父节点，而不会影响兄弟结点，所以它不需要指向兄弟的指针。
B树的分裂：当一个节点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟节点中，再在原结点插入关键字，最后修改父节点中兄弟节点的关键字（因为兄弟节点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟节点之间增加新节点，并各复制1/3的数据到新节点，最后在父节点增加新节点的指针；
从上可知B树分配新节点的概率比B+树要低，空间使用率更高。

胜利贵在坚持，要取得胜利就要坚持不懈地努力，饱尝了许多次的失败之后才能成功。