数据库索引基础

January 11, 2018

数据库索引的简单介绍和使用注意事项

树 #

二叉树 #

性质1：在二叉树中第 i 层的结点数最多为2^(i-1)（i ≥ 1）
性质2：高度为k的二叉树其结点总数最多为2^k－1（ k ≥ 1）
性质3：对任意的非空二叉树 T ，如果叶结点的个数为 n0，而其度为 2 的结点数为 n2，则：n0 = n2 + 1

二叉搜索树 BST #

若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
左、右子树也分别为二叉排序树；
没有键值相等的节点

平衡二叉树 AVL树 #

平衡二叉树（balanced binary tree）,又称 AVL 树。它或者是一棵空树,或者是具有如下性质的二叉树：

它的左子树和右子树都是平衡二叉树，
左子树和右子树的深度之差的绝对值不超过1。

平衡二叉树是对二叉搜索树(又称为二叉排序树)的一种改进。二叉搜索树有一个缺点就是，树的结构是无法预料的，随意性很大，它只与节点的值和插入的顺序有关系，往往得到的是一个不平衡的二叉树。在最坏的情况下，可能得到的是一个单支二叉树，其高度和节点数相同，相当于一个单链表，对其正常的时间复杂度有O(log(n))变成了O(n)，从而丧失了二叉排序树的一些应该有的优点。

B树 #

BTree是平衡搜索多叉树，设树的度为2d（d>1），高度为h，那么BTree要满足以下条件：

每个叶子结点的高度一样，等于h；
每个非叶子结点由n-1个key和n个指针point组成，其中d<=n<=2d,key和point相互间隔，结点两端一定是key；
叶子结点指针都为null；
非叶子结点的key都是[key,data]二元组，其中key表示作为索引的键，data为键值所在行的数据；

B+树 #

B+Tree是BTree的一个变种，设d为树的度数，h为树的高度，B+Tree和BTree的不同主要在于：

B+Tree中的非叶子结点不存储数据，只存储键值；
B+Tree的叶子结点没有指针，所有键值都会出现在叶子结点上，且key存储的键值对应data数据的物理地址；
B+Tree的每个非叶子节点由n个键值key和n个指针point组成；

索引 #

聚簇索引和非聚簇索引（也叫：聚集和非聚集） #

MyISAM 非聚簇索引

...