二叉树(binary tree)
二叉树是经典的数据结构. 他的意义是 : 左子节点小于根节点, 右子节点大于根节点. 没有子节点的节点成为叶子结点; 如图 :
例如我们要查找其中值为3的节点,顺序为 : 7 --> 5 --> 3 --> 4 查找一个深度为d的子节点的运算次数为d;时间复杂度是 O(log(n)).
[复杂度算法 : 设查找次数为k,树的规模为n,那么最多的一次查找数据规模为n,既有 : 2^k = n ,那么k=lg2 n , 记为log(n)] 二叉树的构造比较灵活,同一组数据会有不同的方式 :
对于不同方式的同一组数据构成的不同二叉树,同一个值的检索数据开销是不一样的,因为其平衡性不稳定;
平衡二叉树(avl tree)
针对这种情况,前辈们对二叉树进行了改进,形成了平衡二叉树.它的意义是,每个节点的两个子树深度 d <=1;通过这个约束,他保证了根节点处于中间状态,树的左右两边相对来讲比较均衡,相应的,查询效率也会比较稳定. 当插入,删除或修改某个节点的时候,我们需要建立相应的api对树进行旋转(四种旋转方式 (LL,RR,LR,RL) 对应四种破坏平衡的情况.最多需要旋转两次,具体过程需要参考平衡二叉树的数据结构代码),使变更过的数还能保持平衡性.
平衡多路查找树(balance-tree)
针对于实际情况,操作系统在磁盘中读取数据并不是要谁读谁的,而是以磁盘块为单位(block),每次最少读取一个磁盘块大小的数据,不同的数据库引擎可以规定"页", 即每次读取的最小单位,大部分引擎默认是16k,和系统读取磁盘的最小单位 --磁盘块(block)是一致的.我们也可以用相应的命令设置页的大小.
这个时候我们就知道,如果一个节点在存储一个数据的话, 很明显这样造成了磁盘块的浪费和读取操作的浪费.所以前辈们针对这种情况,在平衡查找树的基础上发展出了平衡多路查找树.
一棵m阶的B-Tree有如下特性：
- 每个节点最多有m个数据.
- 除了根节点和叶子节点外，其它每个节点至少有Ceil(m/2)个数据.
- 若根节点不是叶子节点，则至少有2个数据.
- 所有叶子节点都在同一层，且不包含其它关键字信息.
- 每个非终端节点包含n个关键字信息（P0,P1,…Pn, k1,…kn.
- 关键字的个数n满足：ceil(m/2)-1 <= n <= m-1.
- ki(i=1,…n)为关键字，且关键字升序排序.
- Pi(i=1,…n)为指向子树根节点的指针。P(i-1)指向的子树的所有节点关键字均小于ki，但都大于k(i-1) [引用自: https://www.cnblogs.com/vianzhang/p/7922426.html]
如图,一颗三阶的b-tree树,我们从根节点查找 "2" 数据的过程是 : 一 . 根节点 (第一次I/O) ---->(第一次二分查找) p1 二 . 二级左子节点 (第二次 I/O) ---->(第二次二分查找) p1 三 . 三级左子节点 (第三次次 I/O) ---->(第三次二分查找) 2 很明显,相对于二叉树来讲,降低了I/O操作. 顺便提一下,b-tree树在节点中的数据变更时,变更后也需要维持树的平衡性和多路性,这种机制是依靠b-trere的crud接口实现的.主要思想就是分裂和上推,代码见 : https://www.jianshu.com/p/d2d1181aa93d
b tree
b tree 是b-tree树的一种优化.因为在上述b-tree中讲到,每个节点中,不仅存储数据的key(主键)值,还存储数据的全记录值,这样的话使得每页存储的数据量变小,那相应的树的深度就会增大,此时会引起查找的效率变慢.所以,基于此,前辈们有又想到了,在非叶子结点上只存储key信息,在叶子节点存储key以及key对应的全量信息.这样就能大大的降低树的深度,所以有 : B Tree相对于B-Tree来讲,大部分是一样的,只有几点不同：
- 非叶子节点只存储键值信息。
- 所有相邻叶子节点或首尾子节点之间都有一个链指针,类似于双向链表.
- 数据记录都存放在叶子节点中.
效力分析 :
分页查找和随机查找同时高效支持
通常在B Tree上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。因此可以对B Tree进行两种查找运算：一种是对于主键的范围查找和分页查找，另一种是从根节点开始，进行随机查找。
索引容量大
InnoDB存储引擎中页的大小为16KB，一般表的主键类型为INT（占用4个字节）或BIGINT（占用8个字节），指针类型也一般为4或8个字节，也就是说一个页（B Tree中的一个节点）中大概存储16KB/(8B 8B)=1K个键值（因为是估值，为方便计算，这里的K取值为〖10〗3）。也就是说一个深度为3的B Tree索引可以维护103 * 103 * 103 = 10亿 条记录。
实际情况中每个节点可能不能填充满，因此在数据库中，B Tree的高度一般都在2至4层。mysql的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要1至3次磁盘I/O操作。
主副结合
数据库中的B Tree索引可以分为聚集索引（clustered index）和辅助索引（secondary index）。上面的B Tree示例图在数据库中的实现即为聚集索引，聚集索引的B Tree中的叶子节点存放的是整张表的行记录数据。辅助索引与聚集索引的区别在于辅助索引的叶子节点并不包含行记录的全部数据，而是存储相应行数据的聚集索引键，即主键。当通过辅助索引来查询数据时，InnoDB存储引擎会遍历辅助索引找到主键，然后再通过主键在聚集索引中找到完整的行记录数据。
节选自 : [引用自: https://www.cnblogs.com/vianzhang/p/7922426.html]
