定义

B树（英语：B-tree）是一种平衡的多叉树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成

性质

可以先不看性质（之前不了解的，直接看性质也记不住），直接看性质解析，这里列出来方便后面讲解用。一个m（一般m>=3）阶的B树或是空树、或是满足以下性质的树

1. 根结点至少有两个子女(特殊情况：没有孩子的根结点，即根结点为叶子结点，整棵树只有一个根节点)
2. 每个中间节点都包含k-1个关键字和k个孩子，其中 m/2 <= k <= m
3. 每一个叶子节点都包含k-1个关键字，其中 m/2 <= k <= m
4. 所有的叶子结点都位于同一层
5. 每个节点中的关键字从小到大排列；中间节点的k关键字，左边子树的所有值都必须小于k关键字，右边子树的所有值都必须大于k关键字

性质解析

B树图解.png

• 性质五保证了树的顺序性，才能作为搜索树，达到这一点只需要在插入删除做结构变换时比较下大小就可以了
• 性质二、三、四保证了树的平衡性和磁盘空间利用率；达到性质二、三需要插入删除时注意保持结构一致就可以；达到性质四这里比较巧妙，它是向上分裂的，自然而然的保证了叶子节点都在同一层
• 性质一避免树的单肢

插入、删除动态图

• 插入

  
  Btree添加.gif

• 删除

  
  Btree删除.gif

• 数据结构可视化网站

B+树

定义

B+树是B树的一种变形形式，B+树上的叶子结点存储关键字以及相应记录的地址，叶子结点以上各层作为索引使用

与B树差异

1. 所有关键字都可以在叶子节点中找到，叶子结点本身依关键字的大小自小而大顺序链接。

2. data只存在叶子节点
   如图：

   
   B+树差异.png

相比B树优点

1. 单一节点存储更多元素，减少io次数；因为没有data
2. 更好的范围查找；叶子节点形成了有序链表

常见索引问题与B+树结合看

• 聚集索引和非聚集索引

  • 聚集索引定义：数据行的物理顺序与列值（一般是主键的那一列）的逻辑顺序相同，一个表中只能拥有一个聚集索引。体现在B树里就是聚集索引存储的data是那行的数据，而非聚集索引存储的data是聚集索引的关键字。一张表里一般主键是聚集索引，其余索引为非聚集索引，索引主键不宜过长，因为辅助索引都存储了它

• 索引是越多越好吗

  • 不是的；因为一个是占用存储空间，另一个是，插入删除数据时要维护索引

• like 什么情况可以使用索引、什么情况不能使用索引

  • like xx%可以使用索引；like %xxx、like %xxx%不能使用索引。因为B+Tree是多路平衡搜索树，需要有一个比较值才能走索引，而字符串大小是从左开始比较大小的

• like %xxx%怎么样才能走索引

  • 这个是水哥问的，B+树结构like %xx%是肯定不能走索引的，当时我回答的是用es，感觉也没答好。下来搜索了下，如果不建立全文索引，有两种情况1.搜索的出现在特定稳定，把那个位置的截取出来做索引就可以比较了。。。2.用子查询，像这样 select xx1,xx2,xx3 from xx where 索引列 in(select 索引列 from xx where 索引列 like %x%) 子查询里只查询了索引列会走索引，用索引全扫描代替表的全扫描，如果in里面的数据较少，就存在优化，如果in里面数据很多，就差距不大

• 什么情况下不会走索引

  • 当无法比较值得情况时无法走索引，很简单，因为是搜索树，都没法比较大小了，自然就没法查找下去了。比如说不等于和not in

• 联合索引什么情况下无法使用索引

  • 联合索引就像like的string一样，需要从左边比较大小，因为建立联合索引时，是先从左边开始的，先是第一个排序，当一个相同，再是第二个排序，等等。索引使用联合索引时，举例，(a,b,c)索引，用b,c肯定是无法走索引的，因为没办法通过比较a走到a相同，b,c不一样的搜索树那里