数据库索引
根据前两篇的铺垫，今天我们可以去具体看看索引的知识了。索引的知识以mysql为基本，虽然本人项目使用的PGSql....
B,B+树的性能考量：
我们知道数据库的文件都是存储在磁盘中，那么IO操作就是评价一个索引结构好坏的最好标准。如果这个索引是顺序结构，那么查询一个数据的时间复杂度就是O(N)，数据少还行，到百万，千万级别的时候，查询一次也要O(N)，就意味着N次IO，要命。
而B树则不然，根据第一章的学习，访问B树中最下方的一个节点数据，只发生了3次IO操作（查找了3个高度的节点，最终定位到当前节点中）。而更巧妙的地方在于，数据库系统在设计的时候，一个节点的大小就等于一页的大小（关于页的概念，此文不分析），这就意味着一次IO就能一个节点完全载入其中。
1.B树的时间复杂度是一个渐进式的O(h)=O(log d(N) )。h是树高，d是度，也就是分支的数目，N是总记录数。
2.B树的高度 h=log(m+1)N（不确定，但是估计关系差不多是如此）,假设 数据总量是N，每个节点的数据项是m。由此可知N一定的情况下，m越大，h就越小。而m = 节点的大小/数据项的大小。而节点的大小刚刚说过，大小基本就是确定的，因此如果数据项空间越小，则m就越多，m越多，树的高度h就越小，查找更有利。
这也就是索引字段为什么要小的缘故，小了的话节点的数据项就越多，高度就越小。而B+树内把真是的数据又放在了叶子节点中，非叶子节点中只存放了索引的数据，保证了数据项尽可能的多。保证树的高度。
Mysql中存储引擎的索引实现：
Mysql有两种存储引擎，MyISAM和InnoDB，InnoDB常听说，好像用的也是最多的，MyISAM不常听说。
1.MyISAM使用的是B+树作为引擎，下图展示的是主键索引的示意图：
可以看见索引文件和数据记录其实是分开来的，索引文件里存储的其实是数据记录的地址。
2.MyISAM辅助索引和主键索引类似，但是辅助索引的key可以重复，这是和主键不同的地方。
3.InnoDB的索引实现也是B+树，但是具体的方式确不一样。
3.1第一点，数据文件本身就是索引文件，这一点怎么理解呢？还记得B+树的叶子节点存储了具体数据嘛，在InnoDB里，叶子节点存储的树真正的数据值，而不是MyISAM里存储的是地址。索引的key就是数据表的主键。InnoDB主索引的示意图如下，可以看见叶节点包含了完整的数据记录，这种索引也叫做聚集索引。因为InnoDB的数据文件本身要按照主键聚集，所以必须要有主键。如果没有显示指定，则Mysql会自动选择可以唯一标识的数据列作为主键，如果不存在这种列，则Mysql自动为InnoDB生成一个隐含字段，占位6字节，长整型。
3.2InnoDB辅助索引也和MyISAM不同，辅助索引里面存储的是数据的主键而不是地址，可以这么说InnoDB的辅助索引最终还是要依赖主键索引来实现。下图是以名字为索引的单列索引B+树结构：
3.3辅助索引里面有一个比较特殊的索引叫覆盖索引。它奇特在哪边呢？从3.2我们知道辅助索引的data区域其实存储的是主键的地址，需要通过主键进行再一次定位访问到具体的数据。那么假设：
select uage,uname from user where uage = 12;
如果我们建立的是复合索引(uage,uname)的话，上面一条语句会用到索引，而且能够直接返回出ucard和uname，而不需要再去进行主键定位的操作，这就是特别之处。所以这个复合索引其实可以说成是一种覆盖索引。
那么复合索引的B+树结构是怎么样的呢？这里我们假设user表结构中的联合索引是(age,name,address)。下图不能确认是否是正确的，只是通过参考不同的文章总结出的自己的假设。
通过这个结构我们可以看见，在叶子节点中存储的数据是age,name,address的值（假设这些数据都是按照顺序排列好的，图中是随意写的），那么如果我们只想要这几个值的话，都不需要再进行主键定位查询了，提高了一些效率。
小结：
InnoDB的聚集索引是按照主键搜索，是最高效的，辅助索引需要走两次索引，首先查询辅助索引得到主键，再跟进主键查询获得记录。
问题1：不建议主键字段过长：原因上面第2点也讲过一些，过长会造成数据项空间变大，每个节点数据项数目变少，高度增加。
另外我们发现辅助索引的data域记录的也是主键，因此简介造成辅助索引变大，查询困难。
问题2：非单调字段：如果不是单调字段的话，会造成B+树不断的调整，十分低效，上一篇分析过插入和删除。使用自增字段的话会保持一个相对稳定的顺序。
相关阅读
引言 说白了,数据库的索引问题就是查找问题 数据库索引,是数据库管理系统中一个排序的数据结构,以协助快速查询,更新数据库中表
图（Graph）——非线性数据结构，现实的图结构模型有通信网络，交通网络，人际关系网络等，图结构的组织形式比树结构更为复杂，因此，图结构对存
【有源陶瓷天线构成】GPS天线是由接收天线和前置放大器两个部件组成。GPS接收天线的作用，是将卫星来的无线电信号的电磁波能量变换
前言 数据结构：是指相互之间存在一种或多种特定关系的数据元素的集合用计算机存储、组织数据的方式。数据结构分别为逻辑结构、（存
1.二叉树 1.1 简述 二叉树（binary tree）是一棵树，其中每个节点都不能有多于两个的儿子 左图显示一棵由一个根和两棵子树组成的二