数据库索引及基本优化入门 2013-7-26 一前言 经常在 面试中发现很多人工作了好多年了，项目经验也不少，用过各种数据库，但大都不知道这些SQL语句背后的基本原理，更别说数据库优化了。平时做项目只知道实现功能，懒得学习，懒得思考，懒得看书（其实本人也
数据库索引及基本优化入门
2013-7-26
一 前言
经常在面试中发现很多人工作了好多年了，项目经验也不少，用过各种数据库，但大都不知道这些SQL语句背后的基本原理，更别说数据库优化了。平时做项目只知道实现功能，懒得学习，懒得思考，懒得看书（其实本人也是，不要找借口说这是China国情，项目是给boss做的，但技术和成长是你自己的）。
本篇文章主要讲述数据库索引的基本原理，及基本的数据库优化的知识。所有知识均为本人自己学习的总结以及网络。此篇文章主要是为公司内部人员培训所用的，整理出来只是希望和大家分享、交流，因本人技术有限，若有遗漏、错误，希望多多指正、交流。
二．基础知识 2.1 页
数据库文件存储是已页为存储单元的，一个页是8K（8192Byte），一个页就可以存放N行数据。我们常用的页类型就是数据页和索引页。一个页中除了存放基本数据之外还需要存放一些其他的数据，如页的信息、偏移量等，如下图所示。
虽然SQLServer是以页为单位存储数据，但是其分配空间是以一个盘区为单位的（8个页=64K），这样做的目的主要是为提高I/O的性能。
B树即二叉搜索树，所有非叶子节点最低拥有两个子节点，基本信息如下图所示。都是小的元素放左边，大的元素放右边。比如说要查找某个元素，其时间复杂度就对应该元素的深度，如要查询9，从根节点开始，只要比较三次就找到他了，其查询效率是非常高的。
子节点：最多两个子节点（指针分别指向Left和Right）
阶数（节点子节点个数）：2
深度：就是层数，各个叶子节点不一定一样，如节点21的深度为4，40的深度为3
B-树是一中多路搜索树，其阶数可以自定义（>2)，是很多数据及文件系统应用的一种索引结构，基本特征如：
1) 阶数（M）>2，即孩子数量大于2个
2) 每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
3) 非叶子结点上的多个关键字是按照顺序排列的：K[1], K[2], …, K[M-1]；且K[i]
4) 所有叶子节点都位于同一层，因此叶子节点的深度都是一样的
5) 非叶子结点的关键字个数=指向儿子的指针个数-1；
6) 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
如下图是一个三阶的B-树，节点[18]有两个指针分别指向其2个子节点。
这时如果要插入一个值17，其处理步骤：
1) 从根节点进入，17小于22，进入左边的节点[18];
2) [18]不是叶子节点，继续向下搜索，17小于18，进入其左边的子节点[12,16];
3) [12,16]为叶子节点，插入到该节点；
4) 节点[12,16,17]元素大于2了（3阶树的节点关键字数量应>3/2-1,
5) 12,17分裂成了两个子节点了；
分裂后的效果如下图
以上图片效果来自一个外国大学里面的的在线版B-树的测试，网站：~galles/visualization/BTree.html ，大家可以去这个网站测试，效果很直观，外国人就是牛。本人以前用C#+GDI实现过类似的效果，结果还是可以的，就是当树太大的时候，布局不好处理了。
2.3 B+树
B+树是B-树的变体，也是一种多路搜索树，一棵m 阶的B+树和m 阶的B-树的差异在于：
l 非叶子节点的子节点和其关键字相同，即节点有三个元素（关键字），他就肯定有三个子节点；
l 非叶子节点的子节点P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；
l 所有叶子节点增加一个链指针；
l 所有关键字的数据都在叶子节点中；
如下图所示，图片来自网络（）。
三 索引存储
B+树和B-树是数据库广发应用的索引存储结构，它可以极大的提高数据查找的效率。关于B-树、B+树的原理与应用的详细可以参考文档：
