原文：https://blog.csdn.net/wwh578867817/article/details/50493940
作如下总结与更正：
结构
B+、B树数据结构
它们都是自平衡的搜索树，允许一个节点上有更多的子节点。是专门为外部存储器设计的，对于读取大块数据有良好的性能。
主要影响读取外部存储数据的点
磁盘IO次数
内存大小
拖后腿的磁盘IO次数
传统的平衡二叉树虽然查询性能很好，但是当数据量大的时候就无能为力了。原因有二：1. 数据量大导致内存不够放，只能将数据放入外部存储中。2. 磁盘读写比内存慢很多，越频繁的读写越降低效率。
数据库通过创建索引来提高查询效率。而索引的效率正是依赖磁盘IO次数，快速索引需要有效的减少磁盘 IO 次数。
由于B+、B树多子节点的特性，它们将数据分成了多个区间，每个节点确定的范围更精确。做到一个节点只需要一次IO，降低了树的高度就等于减少IO次数。同时做到不用一次性全部读取数据，只要一个个节点加载到内存中就查询就行了，避免内存不足的问题。
B+、 B树导致的区别
-
B树导致查询速度更快
B树将 key 和 value 都聚合在节点上，而B+树将 value 都存放在叶子节点、内部节点都之存放 Key 副本。所以B树找数据只要找到节点就行，而B+树还得顺着节点副本找到叶子节点上的数据。B树在最好情况下的找效率是O（1），而B+树固定为O（nlogn）
-
B+树增加区间访问性
由于B+树的数据都存放在叶子节点，能够使用磁盘的预读性原理在加载一个节点数据的同时，预加载相邻节点。
-
B+树更适合外部存储
磁盘是分 block 的，一次磁盘 IO 会读取若干个 block，具体和操作系统有关，那么由于磁盘 IO 数据大小是固定的，在一次 IO 中，单个元素越小，量就越大。这就意味着B+树单次磁盘 IO 的信息量大于B树，从这点来看B+树相对B树磁盘 IO 次数少。
采用B树的考量
它适合数据类型简单，性能要求高的场合。前面也说过B树数据聚合的特点能够使查询效率更高。
采用B+树的考量
区间访问常见的情况，而 B树并不支持区间访问。
其次B+树的查询效率更加稳定，数据全部存储在叶子节点，查询时间复杂度固定为 O(log n)。
B+树更适合外部存储。由于内节点无 data 域，每个节点能索引的范围更大更精确
索引
索引是怎么提升性能的？
前面讲了两种兄弟数据结构，那么为什么用它们做索引就能提高查询效率呢？
不使用索引时，执行表查询就是一次全表查询。他会在整张表里没头脑得查找匹配项。而索引基本上是用来存储列值的数据结构，即他把查询范围缩小到列，这使查找这些列值更加快速。如果索引使用 B树 那么其中的数据是有序的。有序的列值可以极大的提升性能。下面解释原因。
假设我们在 Employee_Name这一列上创建一个 B树 索引。这意味着当我们用之前的SQL查找姓名是‘Jesus’的雇员时，不需要再扫描全表。而是用索引查找去查找名字为‘Jesus’的雇员，因为索引已经按照按字母顺序排序。索引已经排序意味着查询一个名字会快很多，因为名字少字母为‘J’的员工都是排列在一起的。另外重要的一点是，索引同时存储了表中相应行的指针以获取其他列的数据。
数据库索引里究竟存的是什么？
- 列值
你现在已经知道数据库索引是创建在表的某列上的，并且存储了这一列的所有值。但是，需要理解的重点是数据库索引并不存储这个表中其他列（字段）的值。举例来说，如果我们在Employee_Name列创建索引，那么列Employee_Age和Employee_Address上的值并不会存储在这个索引当中。如果我们确实把其他所有字段也存储在个这个索引中，那就成了拷贝一整张表做为索引-这样会占用太大的空间而且会十分低效。
- 行指针
如果我们在索引里找到某一条记录作为索引的列的值，如何才能找到这一条记录的其它值呢？这是很简单 - 数据库索引同时存储了指向表中的相应行的指针。指针是指一块内存区域， 该内存区域记录的是对硬盘上记录的相应行的数据的引用。因此，索引中除了存储列的值，还存储着一个指向在行数据的索引。
数据库怎么知道什么时候使用索引？
当这个SQL （SELECT * FROM Employee WHERE Employee_Name = ‘Jesus’ ）运行时，数据库会检查在查询的列上是否有索引。假设Employee_Name列上确实创建了索引，数据库会接着检查使用这个索引做查询是否合理 - 因为有些场景下，使用索引比起全表扫描会更加低效。
如何创建索引？
例子涉及MongoDB和MySQL不同操作，举一例子，具体涉及更多，参看官方文档。
collection.createIndex(Indexes.descending("name"), someCallbackFunction());
CREATE INDEX name_index
ON Employee (Employee_Name, Employee_Age)
使用数据库索引会有什么代价？
那么，使用数据库索引有什么缺点呢？其一，索引会占用空间 - 你的表越大，索引占用的空间越大。其二，性能损失（主要值更新操作），当你在表中添加、删除或者更新行数据的时候， 在索引中也会有相同的操作。记住：建立在某列（或多列）索引需要保存该列最新的数据。
基本原则：只如果表中某列在查询过程中使用的非常频繁，那就在该列上创建索引。
其他索引
除了上述的两种最重要的索引结构以外，还有其他几种索引。
哈希索引
它能以 O(1) 时间进行查找，但是失去了有序性：
无法用于排序与分组；
无法用于部分查找和范围查找；
支持快速精确查找，例如比较字符串是否相等的查询。
MySql的InnoDB 存储引擎有一个特殊的功能叫“自适应哈希索引”，当某个索引值被使用的非常频繁时，会在 B+Tree 索引之上再创建一个哈希索引，这样就让 B+Tree 索引具有哈希索引的一些优点，比如快速的哈希查找。
哈希表索引是怎么工作的
哈系索引的工作方式是将列的值作为索引的键值（key），和键值相对应实际的值（value）是指向该表中相应行的指针。所以在等值查询的时候，直接通过哈希找到引用比全表查询值更快。
全文索引
InnoDB 存储引擎在 MySQL 5.6.4 版本中也开始支持全文索引。
用于查找文本中的关键词，而不是直接比较是否相等。
查找条件使用 MATCH AGAINST，而不是普通的 WHERE。
全文索引使用倒排索引实现，它记录着关键词到其所在文档的映射。
