首先感谢下面各位大佬的文章。
我只是对这些大佬的文章进行一些总结和梳理，
让大家相对系统有效的理解索引的基本原理，并且在不同的场景有一些对比。
图床直接 引用了下面文章中的图，有挂的话。。。 请谅解。
http://www.cnblogs.com/coder2012/p/5309197.html
m-way ,
https://blog.csdn.net/lz201788/article/details/79628726
B- B+ B*
https://blog.csdn.net/zhu_tianwei/article/details/44514861
mongodb mongostat mongotop 命令
https://blog.csdn.net/u012939368/article/details/76696673
mongo 中的索引的原理
https://www.cnblogs.com/morethink/p/9251530.html
B-tree B+tree
https://www.cnblogs.com/mulberries/p/3545990.html
https://www.cnblogs.com/LBSer/p/3322630.html
Bitmap
https://docs.mongodb.com/manual/core/2dsphere/
http://www.mongoing.com/docs/indexes.html
分别为 英文 和中文的
mongodb 支持的索引类型
https://blog.csdn.net/wulex/article/details/79394072
oracle 索引
https://www.cnblogs.com/s-b-b/p/8334593.html
聚集索引 非聚集索引
先谢为敬。
按顺序来，首先介绍常见的索引的类型和特质。
1. b-tree 索引
Oracle数据库中最常见的索引类型是b-tree索引，也就是B-树索引，以其同名的计算科学结构命名。CREATE INDEX语句时，默认就是在创建b-tree索引。没有特别规定可用于任何情况。
2. 位图索引 (bitmap index)
位图索引特定于该列只有几个枚举值的情况，比如性别字段，标示字段比如只有0和1的情况。
3. 基于函数的索引
比如经常对某个字段做查询的时候是带函数操作的，那么此时建一个函数索引就有价值了。
4. 分区索引和全局索引
这2个是用于分区表的时候。前者是分区内索引，后者是全表索引
5. 反向索引（REVERSE）
这个索引不常见，但是特定情况特别有效，比如一个varchar(5)位字段(员工编号)含值（10001,10002,10033,10005,10016..） 这种情况默认索引分布过于密集，不能利用好服务器的并行 但是反向之后10001,20001,33001,50001,61001就有了一个很好的分布，能高效的利用好并行运算。
6.HASH 索引
HASH索引可能是访问数据库中数据的最快方法，但它也有自身的缺点。集群键上不同值的数目必须在创建HASH集群之前就要知道。需要在创建HASH集群的时候指定这个值。使用HASH索引必须要使用HASH集群。
关于B-tree 索引
m-way搜索树
树形索引原理类似于 m-way 搜索树
如果想了解Btree，需要首先了解m-way数据结构。
m-way查找树是是一种树形的存储结构，主要特点如下，
每个节点存储的key数量小于m个
每个节点的度小于等于m
节点key按顺序排序
子树key值要完全小于、大于或介于父节点之间
例如，
3-way如图，m为3，那么每个节点最多拥有为2个（m-1），
待索引元素列表为：
[5, 7, 12, 6, 8, 3, 4]
image
- 上图中展示了m-way 查找树 每个点最多2 个数据，包含 三个数据区间 对应的头部数据。
结合这张图可以理解数据插入时的状态
image
B-tree 的结构
为什么使用B-Tree:一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储在磁盘上，这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。
image
简单理解就是 每个磁盘块 存储了对应的 “数据信息” 和 P1 这种“位置索引” 信息
ps:上面两个概念这么叫仅为了好理解。
B+tree 的结构
image
B+的搜索树与B-树也基本相同，区别是B+树只有达到叶子节点才命中（B-数可以在非叶子节点命中），其性能也等价于在关键字全集做一次二分查找；
【B+的特性】：
1.所有关键字都出现在叶子节点的链表中（稠密索引），且链表中的关键字恰好是有序的。
2.不可能在非叶子节点命中。
3.非叶子节点相当于是叶子节点的索引（稀疏索引），叶子节点相当于是存储（关键字）数据的数据层。
4.更适合文件索引系统。
B*tree 的结构
image
- B*树定义了非叶子结点关键字个数至少为（2/3) *M,即块的最低使用率为2/3(代替B+树的1/2)。
- B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新节点，最后在父亲结点中增加新节点的指针；B+树的分裂只影响原结点和父节点，而不会影响兄弟结点，所以它不需要指向兄弟的指针。
- B*树的分裂：当一个节点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟节点中，再在原结点插入关键字，最后修改父节点中兄弟节点的关键字（因为兄弟节点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟节点之间增加新节点，并各复制1/3的数据到新节点，最后在父节点增加新节点的指针；
- 从上可知B*树分配新节点的概率比B+树要低，空间使用率更高。
B-tree 的性能
一般使用磁盘I/O次数评价索引结构的优劣。先从B-Tree分析，根据B-Tree的定义，可知检索一次最多需要访问h个节点。数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的，在实际实现B-Tree还需要使用如下技巧：
每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。
B-Tree中一次检索最多需要h-1次I/O（根节点常驻内存），渐进复杂度为O(h)=O(logdN)。一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小（通常不超过3）。
B-tree 索引的使用场景
目前
- mongodb使用B-tree
- mysql使用 B+tree
- oracle 使用B*tree
不同的索引对应的m也不太相同
通常 B+ ,B* 相对 B-tree 非叶子节点不存储对应的数据信息所以一般具有更大的m
由于树索引的特性
对于复合索引。
对于三个字段索引
col1 col2 col3
因为索引本身的排布是按照 拼接 col1 col2 col3 进行查找排布
如果直接使用 col2 进行查询是无法命中索引的。
对于这种需要 再建立 col2 ,col3 索引
也就是建立索引需要根据实际使用场景和需求完成对应索引的建立
每个表按照需要经常需要建立多个索引。
bitmap索引
Bitmap索引即位图索引，位图索引是适用于候选值较少却又广泛出现，但不频繁更新的列，比如性别等。
对于类似于 多为分析类的数据库， 如 Hermes
每一列数据都是离散化的。
这样每一列的值都可以 以相对位数较少的 二进制数代表
对于性别这个列，位图索引形成两个向量，男向量为10100...，
向量的每一位表示该行是否是男，如果是则位1，否为0，同理，女向量位01011。
婚姻状态 已婚 未婚 离异
三个状态
分别由三个向量
已婚 10110...
未婚 01001...
离异 10001...
进行查询对应客群时，直接通过对应属性的向量进行二位运算，可以快速定位到对应的条目。
此外，位图索引适合静态数据，而不适合索引频繁更新的列。
举个例子，有这样一个字段busy，记录各个机器的繁忙与否，当机器忙碌时，busy为1，当机器不忙碌时，busy为0。
这个时候有人会说使用位图索引，因为busy只有两个值。
好，我们使用位图索引索引busy字段！
假设用户A使用update更新某个机器的busy值，
比如update table set table.busy=1 where rowid=100;，但还没有commit，而用户B也使用update更新另一个机器的busy值，update table set table.busy=1 where rowid=12; 这个时候用户B怎么也更新不了，需要等待用户A commit。
原因：用户A更新了某个机器的busy值为1，会导致所有busy为1的机器的位图向量发生改变，因此数据库会将busy＝1的所有行锁定，只有commit之后才解锁。
Hash 索引
Hash 索引简单说就是对索引字段的离散化
使进行查询时可以通过离散化规则计算得到对应的位置，进行对应的查询
这种对于查询指定条目的数据性能非常快
但是无法完成常见的 范围搜索查询，排序等操作
mongodb 中的其他索引
mongodb本身还有
multi index 可以对数组字段建索引
地理位置索引
文本索引
等详情可以参考 上文中的官网描述
最后常见的索引 概念中还有 聚集索引和非聚集索引
简单的理解
每个表中 数据是按照一定的规则进行排布并进行存储的，
通常这种排布的依据就是索引。
对于索引和数据排布一致的这种索引 叫 聚集索引
每个表只有一个聚集索引
其他的索引叫做非聚集索引
简单的像就是有个
卡和客户关系表
主键是卡号，有一列是客户号
对于客户号建了索引就是 非聚集索引
主键索引就是 聚集索引
网友评论