数据库索引

结构

Hash结构

哈希表这种结构适用于只有等值查询的场景，比如Memcached及其他一些NoSQL引擎。

BTree结构

BTree又叫做多路平衡搜索树, 一颗m叉到BTree特性如下:

  • 树中每个节点最多包含m个孩子
  • 除根节点与叶子节点外, 每个节点至少有ceil(m/2)个孩子
  • 若根节点不是叶子节点,则至少有两个孩子
  • 所有的叶子节点都在同一层
  • 每个非叶子节点由n个key与n+1个指针组成, 其中ceil(m/2) <= n <= m-1

已5叉BTree为例, key的数量: 2 <= n <= 4, 当n>4时,中间节点分裂到父节点, 两边节点分裂.

关键字插入操作

生成从空树开始，逐个插入关键字。但是由于B_树节点关键字必须大于等于[ceil(m/2)-1],（其中ceil(x)是一个取上限的函数）所以每次插入一个关键字；首先在最底层（叶子节点那一层）的某个非终端节点中添加一个“关键字”，该结点的关键字不超过m-1,则插入完成；否则要产生结点的“分裂”，将一半数量的关键字分裂到新的其相邻右结点中，中间关键字上移到父结点中。

B树结构

B树结构

关键字删除操作

首先查找B树中需删除的关键字,如果该关键字在B树中存在，则将该关键字在其结点中进行删除，如果删除该关键字后，首先判断其结点是否有左右孩子 结点，如果有，则上移孩子结点中的某相近关键字到父节点中，然后是判断移动之后的情况；如果没有，直接删除后，判断删除之后的情况。
删除元素，移动相近元素之后，如果某结点中关键字数小于ceil(m/2)-1,
（m为阶数）则需要看其某相邻兄弟结点是否丰满
如果丰满，则向父节点借一个元素来满足条件；如果其相邻兄弟都刚脱贫，即借了之后其结点数目小于ceil(m/2)-1则该结点与其相邻的某一兄弟结点进行“合并”成一个结点，以此来满足条件。
(结点中关键字个数大于ceil(m/2)-1除根结点之外的结点的关键字的个数n必须满足： ceil(m / 2)-1）<= n <= m-1。m表示最多含有m个孩子，n表示关键字数.)

B+Tree结构

一颗m阶的B+树和m阶的B树的差异在于：

1.非叶子结点的子树指针与关键字个数相同；
2.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）
3.为所有叶子结点增加一个链指针。图中Q是通过指针连在一起的。
4.所有关键字都在叶子结点出现。（5 8 9 10 15 18 20 26 …等等）叶子结点相当于是存储（关键字）数据的数据层；
5.B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中）
6.所有的非终端结点可以看成是索引部分，结点中的关键字是有其孩子指向的子树中最大（或最小）关键字。比如第二层5 它的子树为5 8 9 (而B 树的非终节点也包含需要查找的有效信息)

B+树结构

MySql索引在B+Tree进行优化,在原基础上增加了指向相邻叶子节点的链表指针.就形成了带有顺序指针的B+Tree. 提高区间访问性能

MySql B+树结构

B+树比B树更适合数据库索引？

1、 B+树的磁盘读写代价更低：B+树的内部节点并没有指向关键字具体信息的指针，因此其内部节点相对B树更小，如果把所有同一内部节点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多，一次性读入内存的需要查找的关键字也就越多，相对IO读写次数就降低了。

2、B+树的查询效率更加稳定：由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

3、由于B+树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以B+树更加适合在区间查询的情况，所以通常B+树用于数据库索引。

索引分类

类别:

  1. BTREE索引
  2. 位图索引
  3. 函数索引

分类:

  1. 单值索引: 一个索引只包含一列

  2. 唯一索引: 索引列的值必须唯一, 可以为NULL

  3. 复合索引(覆盖索引): 一个索引包含多列

    由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段。

    最左前缀原则:

    ​ 联合索引的最左 N 个字段，也可以是字符串索引的最左 M 个字符

    ​ 如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的

    索引下推:

    ​ 在MySQL5.6之前，只能从根据最左前缀查询到ID开始一个个回表。到主键索引上找出数据行，再对 比字段值。MySQL5.6引入的索引下推优化，可以在索引遍历过程中，对索引中包含的字段先做判 断，直接过滤掉不满足条件的记录，减少回表次数。

    如果查询条件使用的是普通索引（或是联合索引的最左原则字段），查询结果是联合索引的字段或是主键，不用回表操作，直接返回结果，减少IO磁盘读写读取正行数据

索引设计原则

  • 查询频次高, 数据量比较大 [建立索引]

  • 索引字段的选择, 经常where子句中创建索引, 挑选最常用、过滤效果最好的列的组合 [建立索引]

    如果读取字段索引中不存在(索引只包含索引字段和主键字段),需要回到主键索引树搜索的过程(回表). 大大降低执行开销. 尽量减少回表操作.

  • 最好使用唯一索引, 区分度越高, 使用索引的效率越高 [建立索引]

  • 索引不是越多越好, DML操作时需要维护索引, 多条索引选可用索引提高了选择代价.

    一个数据页满了，按照B+Tree算法，新增加一个数据页，叫做页分裂，会导致性能下降。空间利用率降低大概50%。当相邻的两个数据页利用率很低的时候会做数据页合并，合并的过程是分裂过程的逆过程。

  • 尽可能使用短索引, 提高索引访问I/O的效率, 构成索引的字段总长度比较短,那么在给定大小的存储块内可以存储更多的索引值,提高I/O效率.

  • 利用最左前缀, N个列组合而成的组合索引, 那么相当于是创建N个索引, 如果查询时where子句使用了组成该索引的前几个字段,那么这条查询SQL可以利用组合索引来提升查询效率. 

    1
    		 
    CREATE INDEX idx_name ON tab_name (NAME, EMAIL, STATUS)

    就相当于对name创建索引、NAME+EMAIL创建索引、NAME+EMAIL+STATUS创建索引

  • 主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小

    普通索引数据字段使用主键值

    从性能和存储空间方面考量，自增主键往往是更合理的选择

索引技巧

  • 重建主键的索引最好不要删除主键索引.

    不论是删除主键还是创建主键，都会将整个表重建

    可以使用 alter table T engine=InnoDB来重键索引

 上一篇