不得不看的B树索引

索引

一、先导：
要想了解B 树索引，首先要了解树的数据结构，二叉树，平衡二叉树，B-树，B+树。
1、二叉树： 每个结点最多有两个子树的树结构
二叉树的特性：

• 每个结点都包含一个元素和n个子树，0<=n<=2
• 左子树和右子树是有顺序的，次序不能颠倒。左子树的值小于父结点的值，父结点的值小于右子树的值

练习：[31 18 73 9 27 37 99]
上面数据经过一系列插入后：变成了有序的结构,且符合二叉树的特性

但是如果是同一组数[9 18 27 31 37 73 99]，升序后再排序：

这种情况出现了严重的倾斜,这是比较极端的情况 ，二叉树变成线性结构了，查询效率明显降低，没有发挥出二叉树的优势。
为了不让二叉树出现严重倾斜，提出了平衡二叉树的概念。
2、平衡二叉树： 特殊的二叉树
比二叉树多了一个特性：
左右2个子树的高度差的绝对值不会超过1，并且左右2个子树都是平衡二叉树。
一个平衡二叉树最多能容纳：2⁰+ 2¹+2²+…+2^h-1,h为高度。
这样计算100w的数据，高度为20，从有着100w条数据的平衡二叉树中找一个数据最多20次，如果是内存，效率很高，但是数据库中的数据基本上是放到磁盘的,每读取一个二叉树结点就是一次磁盘IO,找一条数据，经过20次磁盘IO,性能就很差了。于是考虑把平衡二叉树压缩（由高变成胖），即B-树。

3 、B-树 ：
特性：

• 每个结点最多m个子结点。
• 除了根结点和叶子结点外，每个结点最少有m/2（向上取整）个子结点。
• 如果根结点不是叶子结点，那根结点至少包含两个子结点。
• 所有的叶子结点都位于同一层。
• 每个结点都包含k个元素（关键字），这里m/2≤k<m，这里m/2向下取整。
• 每个节点中的元素（关键字）从小到大排列。
• 每个元素（关键字）字左结点的值，都小于或等于该元素（关键字）。右结点的值都大于或等于该元素（关键字）。

我们都知道数据库的数据是一条条存在的。
思考： 数据库以B-树数据结构存数数据，数据是如何存放的呢？

把元素部分拆成了key-data形式，key就是主键，data就是数据。
4、B+树：
B+树是在B-树基础上的一个优化。
特点：

• 所有的非叶子节点只存储关键字信息。
• 所有卫星数据（具体数据）都存在叶子结点中。
• 所有的叶子结点中包含了全部元素的信息。
• 所有叶子节点之间都有一个链指针。
  B+树：
  
  思考：B-Tree or B+Tree？
  首先我们得知道：操作系统从磁盘读取数据到内存是以磁盘块（block）为基本单位的，位于同一个磁盘块的数据会被一次性读取出来,而不是需要什么读取什么。即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这是因为计算机中有个著名局部性原理：一个数据被用到时，其附近的数据也通常会马上被使用。

优缺点：

• B-树因为非叶子节点会保存具体数据，查找关键字的时候找到即可返回。而B+树的所有数据都存在叶子结点，每次查找都得到叶子结点。所以同样高度情况下，B-树效率更高；
• 由于B+树的所有数据都存在叶子结点上，并且叶子结点有指针连接，在找大于或小于关键字的时候，B+树只要找到关键字，然后沿着链表遍历就行，而B-树需要遍历该关键字结点的根结点去搜索；
• 由于B-树的每个结点（这个结点可以理解为一个数据页）都存储主键+实际数据，而B+树非叶子结点只存储关键字信息，而每一页大小是有限的，所以同一页B-树能存储的数据肯定比B+树少，那么同样总量的数据，B-树的深度更深，增大查询时的磁盘I/O次数。
  故，常用的关系型数据库都选择B+树的数据结构来存储数据。
  二、索引的结构：
  B+树索引：
  

二、索引的使用：
创建索引原则：

• 业务查询条件
• 数据量大小，包括今后一段时间内的数据量
• 数据分布情况
• 单表索引一般不超过5个

索引使用条件：

• 前导列使用
• 表数据量，实际取数量

三、索引的分类：
B树，函数，位图，反序，反向，分区

四、索引的运维： 索引的作用：保证业务的完整性 索引的优点：提高查询速度 索引的缺点：增加存储空间，降低DML语句的效率 索引虽然能加快检索速度，但是在有些情况下，使用索引查询一样会很慢，这时候需要分析数据，考虑重建索引