二分法则延申
- 平衡二叉树，B树，B+树都是基于二分法则的延申。B树和B+树的主要区别是B+树会存储索引节点的数据。
- 二分法的数据结构主要核心是找准中点，因为数据的不断写入会导致中点的不断变化，这部分是基于二分法的优化的重点。
散列索引
- 链表：链表索引通过多级链表进行数据索引存储，通过跳表的形式快速查到数据，比较适合等值查询，如果要做范围查询是不支持的。（所以Clickhouse不支持范围查询）
- 哈希：通过哈希算法把数据散列存储，能保证数据的均匀分配，但同样也不支持等值查询，不支持范围查询，比较多用于内存的计算。
- 位图：通过将数据进行格式行转列存储对数据进行标签，读取数据的时候可以直接按标签读取。快速查询数据。
Key_Value
- 倒排：把文本存储成Key_Value。把Key存储成要找的词语，Value记录成文档ID。通过查找Key快速找到所属文档。
- 字典树：把文档分词存储成二分法树状结构，快速查找。
- LSM树：通过数据的时间序列存储把新进来数据放到最后面并进行标记，然后再进行索引合并。
平衡二叉树
基于二分法的策略的数据结构;
先通过排序对数据进行组装,利用二分法思路组成树状结构,减少无关的数据检索.
操作数据时不同步Update树结构，需要定期利用Treap,红黑树等算法可以保证数据的平衡
查询性能和树的层级成反比例,为了保证树的层级均衡,必须要保证树的两端大致平衡;
操作数据特点：
写入数据时：根据路径找到位置后,直接在位置中写入;如果存在写入数据在前步骤范围内,也不处理
删除数据时：如果删除的是分支节点，会延下最小的分支找到最大的节点进行替换；先走左边分支，再往下找最大的数；
https://www.cs.usfca.edu/~galles/visualization/BST.html
B树(B-tree)
平衡二叉树升级版,支持多路分支;操作数据同步Update树结构;
每个节点可以存在多个分支(Max.Degree).通过在节点中增加判断分支,减少树的高度
对比平衡二叉树,每次插入数据的时候都会检查并调整树的结构,确保树状结构的健康;(但也带来性能影响)
整颗树就是一个节点都是数据.搜索到结果就可以结束
B+树
B+树是B树的升级版,更充分利用节点的空间,让查询速度更稳定;
只有叶子节点保存数据或指针,每次查找都要渠道叶子节点获取数据
非叶子节点用于索引数据,非叶子节点的判断空间,减少磁盘IO
B+树会为所有叶子结点增加一个链指针，便于区间查找和遍历。
对比数据紧密型更高,缓存命中率也会比B树高;
附加特点:
聚集索引:叶节点保存完整索引数据
非聚集索引:叶节点保存物理指针
辅助索引:叶节点保存逻辑指针
一般数据库应该较多的为B+树索引
B+树索引结合磁盘的性能应用
根据B树和B+树的定义,检索一次最多需要访问h个节点
数据库设计巧妙利用磁盘预读原理(磁头寻道后,会把磁道附近的数据也读到内存操作),将一个节点的大小设为等于一个页,这样每个节点只需要一次IO即可完全载入.
B+树在非叶子节点去除了Data域,因此拥有更大出度(dmax=pagesize/(keysize+datasize+pointsize)),更好的性能.
B,B+树索引使用
索引大大减少了存储引擎需要扫描的数据量
索引可以帮助我们进行排序以避免使用临时表
索引可以把随机IO变成顺序IO
选择索引的办法:
有主键的列一定要建立索引(InnoDB一定要使用自增的主键索引,保持磁盘写数据的连续性)
有外键的列要建立索引,加快表关联
经常范围查询或排序的列最好建立索引
经常Where子句的列最好建立索引
组合索引需要满足最左前缀匹配(组合A,B,C.查询时,不能跳过B,如果要跳过,可以在语句中把B列In出来,或者使用辅助索引)
索引不支持带函数的转化,需要自己手动转化
MySQL索引及其实现原理(基于MyISAM及InnoDB引擎)
mysql索引之一：索引基础（B-Tree索引、哈希索引、聚簇索引、全文(Full-text)索引区别）（唯一索引、最左前缀索引、前缀索引、多列索引）
链表索引
通过设计多层链表，对数据进行多次的分层，每次分层节点会更加细致;
上层链表的节点，在下层链表中也有相同节点，以便在上次链表找到定位后，快速跳到下层链表继续搜索；
增加数据的时候通过一个概率值来决定是否需要添加上层节点。实现起来比较局部。不会像B树那样牵一发动全身。
哈希索引
通过哈希算法把数据转换成对应的哈希码.并把数据指针保存在哈希表对应的哈希码中;
哈希索引没有对索引值进行排序,不支持范围查询和排序,只支持等值查询;
当发生哈希冲突时,存储引擎必须遍历链表中的所有行指针;
LSM树
基于内存和磁盘的存储转换的存储方式
把最新的数据驻留在内存中，等到积累到足够多之后，再使用归并排序的方式将内存内的数据合并追加到磁盘队尾(因为所有待排序的树都是有序的，可以通过合并排序的方式快速合并到一起)
通过批量存储技术规避磁盘随机写入问题,LSM树牺牲了部分读性能,用来大幅提高写性能.
可以保证数据写入的连续性,但会导致数据会用冗余,需要取key最新一条的数据.
LSM-tree在某些情况下，特别是在查询需要快速响应时性能不佳。通常LSM-tree适用于索引插入比检索更频繁的应用系统(例如HBase)
LSM树详解
位图索引
多用于OLAP查找列值基数较小的场景.
通过将列值内容陈列开来,形式二维表格形式,在重新组织成位图形成的索引
位图索引不适合并发环境，在并发环境下可能会造成大量事务的阻塞
详解oracle bitmap位图索引_ezbit-CSDN博客
倒排索引
正向索引:文档ID是Key,文档中的词语是Value
倒排索引:文档中的词语是Key,文档ID是Value
通过Key,Value倒置,方便搜索引擎的关键字搜索.
通过分词器对文档进行分词,然后记录到每个词语对应的文档ID,并记录到对应的词频
生成的单词词典,一般会优化数据结构,两种形式
哈希链表:通过对单词做哈希压缩保存,通过链表对哈希冲突的单词进行分解处理;
B,B+树:底层节点就是每个单词,通过B,B+树提升找到单词的速度;
什么是倒排索引？
字典树索引
主要应用于Lucene,关键词提示,自动补全,敏感词过滤系统
优化思路(转换数据类型):将每个节点中的数组换成其他数据结构，比如有序数组(可以二分查找)、跳表、散列表、红黑树等。
优化思路(压缩树结构):对只有一个子节点的节点，而且此节点不是一个串的结束节点，可以将此节点与子节点合并
Trie|如何用字典树实现搜索引擎的关键词提示功能
