索引是帮组MYSQL高效获取数据的排好序的数据结构
二叉树
二叉树是树节点的度不大于2的有序树。它是一种最简单最重要的树。
二叉树的左节点始终小于父节点。二叉树的有节点始终大于等于父节点
对于单边递增的数据，二叉树会变成链表的形式。这个时候查询不会减少次数。所以也不会减少IO次数。这就是MYSQL没有使用二叉树的原因。
@Data
public class NodeTest {
int fData; //数据
NodeTest leftChild; //左节点
NodeTest rightChild; //右节点
public NodeTest() {
}
public static void main(String[] args) {
NodeTest nodeTest = new NodeTest();
}
static class Tree{
private NodeTest root;
public boolean insertNode(NodeTest root1,NodeTest nodeTest){
if (root == null){
root = nodeTest;
return true;
}else {
// 代表不为null
if (root1 == null){
root1 = root;
}
int fData1 = root1.getFData();
if (fData1 > nodeTest.getFData()){
// 左节点
if (root1.getLeftChild() == null){
root1.setLeftChild(nodeTest);
return true;
}else {
// 左节点不为null
insertNode(root1.getLeftChild(),nodeTest);
}
}else {
// 左节点
if (root1.getRightChild() == null){
root1.setRightChild(nodeTest);
return true;
}else {
// 左节点不为null
insertNode(root1.getRightChild(),nodeTest);
}
}
}
return false;
}
public static void main(String[] args) {
Tree tree = new Tree();
NodeTest nodeTest = new NodeTest();
nodeTest.setFData(3);
boolean b = tree.insertNode(null, nodeTest);
NodeTest nodeTest1 = new NodeTest();
nodeTest1.setFData(5);
tree.insertNode(null,nodeTest1);
NodeTest nodeTest2 = new NodeTest();
nodeTest2.setFData(2);
tree.insertNode(null,nodeTest2);
NodeTest nodeTest3 = new NodeTest();
nodeTest3.setFData(3);
tree.insertNode(null,nodeTest3);
System.out.println(b);
}
}
}
红黑树
- 每个结点不是红色就是黑色
- 根节点是黑色的
- 如果一个节点是红色的，则它的两个孩子结点是黑色的（不会出现连在一起的红色节点）
- 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点（在计算一条路径中黑色节点个数的时候要带上叶子节点，因为叶子节点也是黑色的，也就是空节点）。
- 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)（为了保证空树也是红黑树）
- 红黑树确保没有一条路径会比其他路径长出俩倍（红黑树前面的性质保证了当前的性质）
虽然红黑树会根据性质做出对应的旋转，能够减少树的层级。但是对MYSQL而言存储的数据都是十万百万级别的。对应的树的层级还是很高。进行的IO次数也是不可避免的。所以MYSQL也没有使用红黑树（java中的Map和Set存储数据时如果一个桶上的数据大于8的时候会把链表转换为红黑树）。
B树
B 树也称 B- 树,它是一颗多路平衡查找树。我们描述一颗B树时需要指定它的阶数，阶数表示了一个结点最多有多少个孩子结点，一般用字母m表示阶数。当m取2时，就是我们常见的二叉搜索树。
一颗m阶的B树定义如下：
1）每个结点最多有m-1个关键字。
2）根结点最少可以只有1个关键字。
3）非根结点至少有 Math.ceil(m/2)-1个关键字。
4）每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
5）所有叶子结点都位于同一层，或者说根结点到每个叶子结点的长度都相同。
B-树每个节点都可以存储多个数据。而且也有红黑树的旋转属性。所以存储数据相同的情况下B数的层级更小。所以IO次数就会少。但是由于每个节点的数据都会存储真实的数据，真实数据往往比较大。所以导致一层节点存储的数据是有限的。所以MYSQL也没有用B树做为索引的存储结构。会用到下面的B+ 树。
B+ 树
B+ 树是B树的一个变种。B+ 树的非叶子节点不在存储数据。只进行数据索引。叶子节点结构也是有序的。并且每个元素会存储下一个元素的索引和上一个元素的索引。这样就大大增加了每一层非叶子节点存储的数据索引质量了。
假如一个节点能存储16KB、索引占用10b、数据占用1Kb则三层树可以存储多少？
| 结果\层 | B | B+ |
|---|---|---|
| 1 | 16 | 1600 |
| 2 | 16 * 16 = 256 | 1600 * 1600 = 2560000 |
| 3 | 256 * 16 = 4096 | 2560000 * 16 = 40960000 |
大概算了下发现B+ 比 B多存储了四个量级的数据。所以B+ 树IO次数在大数据两下比B树要小的多。
主键索引和联合索引的区别
- 主键索引是聚簇索引、联合索引是非聚簇索引。
- 主键索引推荐用int类型并且是自增的（减少B+树的旋转和调整）。并且聚簇索引叶子结点存储的是一条数据的所有值。非聚簇索引存叶子结点存储的是主键id。所以如果使用非聚簇索引查询数据，然后使用select * 还需要获取id数据后进行主键索引树中进行回表查询。所以会浪费一部分时间。
- 为啥非聚簇索引不存储一整行数据
- 为了保证数据一致性和节省空间。
- 因为如果索引都存储所有的数据。那每个索引在数据修改的时候都要更改为最新的数据。这个就无法保证了数据的一致性。
- 非聚簇索引不保存全部数据就可以减少很都空间。
- 为了保证数据一致性和节省空间。
索引覆盖
通俗来讲就是在执行某个查询语句时进行，在一个索引树（非聚簇索引）上就能查询到需要的字段、而无需回了，这就是索引覆盖。正确是使用好索引覆盖可以减少sql的执行时间。
比如：
创建一个user表：
creat table user（
id int primary key，
name varchar(20),
sex varchar(5)
) engine=innodb;
ALTER TABLE user ADD INDEX index_name (name);: 添加name字段普通索引
如果查询
select id,name,sex from user where name = ‘小白’;
这个sql会先查询name索引树获取符合条件的id列表。然后再回表查询主键索引树获取sex字段数据。这就要拆线呢两次数据。
如果创建一个联合索引就可以不用多查询一次了。
ALTER TABLE user ADD INDEX index_name_sex (name,sex);: 添加name字段普通索引;
这样就拆线呢一次就能获取到所有需要的字段了。
结果：
所以在给表创建索引的时候最好创建联合索引。不要创建单个索引，一张表可以用两三个联合索引能概括全你所有的查询。不要使用select * 查询数据。每次查询最好返回自己有用的数据。不要返回无用的。
