[TOC]
高级数据结构
Hash表，Hash索引
数据库Hash索引参考：https://blog.csdn.net/olizxq/article/details/82313489
Hash索引不像B-Tree 索引需要从根节点到枝节点，最后才能访问到页节点这样多次的IO访问，所以 Hash索引的查询效率要远高于 B-Tree 索引
hash索引的限制
- 哈希索引只包含哈希值和行指针，而不存储字段值，所以不能使用索引中的值来避免读取行。
- 哈希索引数据并不是按照索引值顺序存储的，所以也就无法用于排序。
- 哈希索引也不支持部分索引列匹配查找，因为哈希索引始终是使用索引列的全部内容来计算哈希值的。
- 哈希索引只支持等值比较查询，包括=、IN()、<>（注意<>和<=>是不同的操作）。也不支持任何范围查询，例如
WHERE price>100。 - 访问哈希索引的数据非常快，除非有很多哈希冲突（不同的索引列值却有相同的哈希值）。当出现哈希冲突的时候，存储引擎必须遍历链表中所有的行指针，逐行进行比较，直到找到所有符合条件的行。
- 如果哈希冲突很多的话，一些索引维护操作的代价也会很高。例如，如果在某个选择性很低（哈希冲突很多）的列上建立哈希索引，那么当从表中删除一行时，存储引擎需要遍历对应哈希值的链表中的每一行，找到并删除对应行的引用，冲突越多，代价越大。
B Tree
多路搜索树, 关键字集合分布在整棵树中(非叶子节点和叶子节点都有关键字)
局部性原理与磁盘预读
由于磁盘的存取速度与内存之间鸿沟,为了提高效率,要尽量减少磁盘I/O.磁盘往往不是严格按需读取，而是每次都会预读,磁盘读取完需要的数据,会顺序向后读一定长度的数据放入内存。
磁盘IO 与 B Tree 应用
磁盘读取依靠的是机械运动，分为寻道时间、旋转延迟、传输时间三个部分，这三个部分耗时相加就是一次磁盘IO的时间
数据库索引是存储在磁盘上，当表中的数据量比较大时，索引的大小也跟着增长，达到几个G甚至更多。当我们利用索引进行查询的时候，不可能把索引全部加载到内存中，只能逐一加载每个磁盘页，这里的磁盘页就对应索引树的节点。当访问一个地址数据的时候，与其相邻的数据很快也会被访问到。每次磁盘IO读取的数据我们称之为一页（page）。一页的大小与操作系统有关，一般为4k或者8k。这也就意味着读取一页内数据的时候，实际上发生了一次磁盘IO。
减少磁盘IO的次数就必须要压缩树的高度
B树主要应用于文件系统以及部分数据库索引
B+ Tree
定义
- 树中每个非叶结点最多有 m 棵子树；
- 根结点 (非叶结点) 至少有 2 棵子树。除根结点外, 其它的非叶结点至少有 ém/2ù 棵子树；有 n 棵子树的非叶结点有 n-1 个关键码。
- 所有叶结点都处于同一层次上，包含了全部关键码及指向相应数据对象存放地址的指针，且叶结点本身按关键码从小到大顺序链接；
- 每个叶结点中的子树棵数 n 可以多于 m，可以少于 m，视关键码字节数及对象地址指针字节数而定。
- 若设结点可容纳最大关键码数为 m1，则指向对象的地址指针也有 m1 个。
- 结点中的子树棵数 n 应满足 n 属于[m1/2, m1]
- 若根结点同时又是叶结点，则结点格式同叶结点。
- 所有的非叶结点可以看成是索引部分，结点中关键码 Ki 与指向子树的指针 Pi 构成对子树 (即下一层索引块) 的索引项 ( Ki, Pi )，Ki 是子树中最小的关键码。
- 特别地，子树指针 P0 所指子树上所有关键码均小于 K1。结点格式同B树。
- 叶结点中存放的是对实际数据对象的索引。
在B+树中有两个头指针：一个指向B+树的根结点，一个指向关键码最小的叶结点。
B+ tree 与 B tree 的不同之处
所有关键字存储在叶子节点，非叶子节点不存储真正的data
- 为所有叶子节点增加了一个链指针
B+ tree 数据库索引
B+ tree 优势
B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快；
B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定；
B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高；
B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描；
红黑树
性质1. 节点是红色或黑色。 性质2. 根节点是黑色。 性质3. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点) 性质4. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
从根到叶子的最长的可能路径不多于最短的可能路径的两倍长
红黑树高度依然是平均log(n)，且最坏情况高度不会超过2log(n)。
任何不平衡都会在3次旋转之内解决， 红黑树能够以O(log2(N))的时间复杂度进行搜索、插入、删除操作
Trie Tree(字典树)
参考：https://blog.csdn.net/qq_26437925/article/category/5773761
Log Structured Merge Trees（日志结构的合并树）
磁盘的读写快慢问题
顺序读写磁盘（不管是SATA还是SSD）快于随机读写主存，而且快至少三个数量级