微信号:java_bj

介绍:从算法基础到常用框架的知识体系,从初级程序员到高级架构师的成长之路,从创业小团队到Google、BAT的工作机会,始于JAVA而又不止于JAVA.JAVAer在北京,我们一起成长.

数据库系列七:二叉树、B树、B+树、B*树和索引

2016-08-11 00:26 FieldSheng
点击上方“Java北京”关注我们


在《数据库系列五:关于SQL,你应该知道的事儿》里面我们简单提到了索引以及索引实现的方式,对于索引实现的具体原理没有展开叙述。今天我们以最常见的B树索引为例,来说说索引实现的原理。

一、Binary Tree(二叉树)、Binary Search Tree(二叉排序树)

讲B树之前,先要说说Binary Tree,因为很多同学会误以为B树就是Binary Tree——二叉树,二叉树的每个节点最多有两个子节点(Left和Right)。在这里,我们只讨论二叉搜索树这种特殊的二叉树(Binary Search Tree,也叫二叉排序树,Binary Sort Tree),二叉搜索树的每个节点都只存储一个键值,并且左子树(如果有)所有节点的值都要小于根节点的值,右子树(如果有)所有节点的值都要大于根节点的值。


我们可以利用二叉搜索树进行键值的查找,使用B树进行键值查找时,从根节点开始,如果查询的关键字与节点的关键字相等,那么就命中返回;否则,如果查询关键字比节点关键字小,就进入左子树;如果比节点关键字大,就进入右子树;如果要进入的子树为空,则说明找不到相应的键值。

 当二叉搜索树的所有非叶子节点的左右子树的节点数目均保持差不多时(平衡),这时B树的搜索性能逼近二分查找;并且它比连续内存空间的二分查找更有优势的是,改变B树结构(插入与删除结点)不需要移动大段的内存数据,甚至通常是常数开销。

特殊情况下,根节点的左右子树的高度相差不超过1时,这样的二叉树被称为平衡二叉树;与之相对的是,二叉搜索树有可能退化成线性树。


 二、B-Tree(Balanced Tree,B树,B-树)

值得说一句的是,B树的英文名称为B-Tree,中间这个-不是minus,而是作为连接符的横杠,国内很多人把其译为B-树,与B+树对应,实际上B-树和B树就是同一种数据结构。

B树是一种平衡的多路搜索树(非二叉),它的特点是:

  • 任意非叶子节点最多可以有M个子女,且M>2;

  • 根节点的子女数为[2, M];

  • 除了根节点以外的非叶子节点的子女数目为[M/2, M];

  • 每个节点存放至少M/2-1(取上整)和至多M-1个键值(至少两个);

  • 非叶子节点的关键字个数=指向子女的指针个数-1;

  • 非叶子节点的关键字K[1],K[2],…,K[M-1]且K[i] < K[i+1];

  • 非叶子结点的指针:P[1], P[2], …, P[M];其中P[1]指向关键字小于K[1]的子树,P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1], K[i])的子树;

  • 所有叶子节点都位于同一层(这才能叫Balanced Tree嘛)。

B树与上面的二叉搜索树的区别是它的每个节点可以存不止一个键值,并且子女可以不止两个,所以同样数量的关键值,B树比二叉搜索树更矮一些。


使用B树进行搜索时,从根节点开始,对节点内的键值进行二分查找,如果命中则结束,否则进入查询键值所属范围的子女结点。其搜索性能等于键值组成的全集中做一次二分查找的效率,即O(log2N)。

三、B+Tree(B+树)

B+树是B树的变种,也是一种平衡的多路搜索树。它与B树的主要区别是:

  • 非叶子结点的子树指针与关键字个数相同;

  • 非叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1])的子树(B树是开区间,B+树是左开右闭);

  • 为所有叶子结点增加一个链指针;

  • 所有关键字都在叶子结点出现。


使用B+树搜索的原理与B树大体相同,除了B+树必须到达叶子节点才可以命中,其效率也相当于二分查找。

往B+树种添加数据,当一个节点满时,分配一个新的节点,并将原节点中1/2的数据复制到新节点,最后在父节点中增加新节点的指针。所以B+树的分裂只影响原节点和父节点,而不会影响其他节点。

 四、B*Tree(B*树)

B*树又是B+树的变种,它是在B+树的非根和非叶子结点再增加指向兄弟的指针。另外,B*树规定非叶子节点的键值个数至少为(2/3)* M,这样块的使用率就从B+树的1/2上升为2/3,所以其空间使用率更高。


当向B*树种添加数据,一个节点满时,如果它的下一个兄弟节点未满,那么将一部分数据移到兄弟节点中,再在原节点插入键值,最后修改父节点中兄弟节点的键值(因为兄弟节点的键值范围改变了);如果兄弟也满了,则在原节点与兄弟节点之间增加新节点,并各复制1/3的数据到新节点,最后在父节点增加新节点的指针。这样来看,B*树分配新节点的概率也是要比B+树要低的。

 五、索引

说了这么多,终于到索引出场了。

数据库的数据是以块的形式存储在磁盘中的(磁盘上的数据块与链表类似,一个数据块包含一个数据段和一个指向下一个数据块的指针——这样可以有效利用磁盘空间,进行非连续存储)。假设一个数据库表在磁盘上占据了N个数据块,查询某个字段时,平均要进行N/2次查找,对于百万千万级别的数据库表来说,这种查找方式简直要了命。

上面介绍的几种数据结构,插入数据的同时进行了数据的排序,我们设想,如果数据表的某个数据字段根据上述数据结构存储,我们就可以利用二分查找达到O(log2N)的性能。直观暴力地对比一下:1000w条记录,假设每条记录大小500Byte,数据库所在操作系统的数据块大小为4KB,即每个数据库大约存储8条记录,1000w条记录需要数据块125w个,N/2大约是log2N的3w+倍(62.5w/20),实际上,因为B树和B+树等每个节点都会存储多于两个键值,所以需要查询的数据块还会小于log2N。注意,为了简化说明过程,我们这里没有考虑计算机根据局部性原理(当一个数据被用到时,其附近的数据也通常会马上被使用)进行的预读。

索引就是这种神奇伟大的存在。索引相当于数据库的表数据之外新建的数据结构,该数据结构的数据段中存储着字段的值以及指向实际数据记录的指针。

聚集索引和非聚集索引的示例图如下:

聚集索引:聚集索引数据列的顺序就是表记录的物理存储顺序,如下图。



非聚集索引:


六、关于索引优化

关于建索引的一些原则和注意点:

  1. 尽量选择区分度高的列作为索引,区分度的公式是 count(DistinctCols) / count(*),表示字段不重复的比例,比例越大我们扫描的记录数越少,唯一键的区分度是1,而一些状态、性别字段可能在大数据面前区分度就是0(一般要求区分度在0.1以上)

  2. 尽量的扩展索引,不要新建索引。比如表中已经有a的索引,现在要加(a,b)的索引,那么只需要修改原来的索引即可。(a,b)的索引对只对a进行查询的情况有效。

  3. 何时建立索引应当遵循以下原则:该表常用来在索引列上查询,该表不常更新、插入、删除等操作。更新、插入、删除操作会对索引的树结构进行重新维护,造成较大的资源开销。索引并不是越多越好,索引固然可以提高相应的 select 的效率,但同时也降低了 insert 及 update 的效率,因为 insert 或 update 时有可能会重建索引,所以怎样建索引需要慎重考虑,视具体情况而定。

  4. 应尽可能的避免更新clustered索引数据列,因为 clustered索引数据列的顺序就是表记录的物理存储顺序,一旦该列值改变将导致整个表记录的顺序的调整,会耗费相当大的资源。若应用系统需要频繁更新 clustered索引数据列,那么需要考虑是否应将该索引建为 clustered索引。

  5. 最左前缀匹配原则,非常重要的原则,mysql会一直向右匹配直到遇到范围查询(>、<、between、like左匹配)就停止匹配,比如a = 1 andb = 2 and c > 3 and d = 4 如果建立(a,b,c,d)顺序的索引,d是用不到索引的,如果建立(a,b,d,c)的索引则都可以用到,a,b,d的顺序可以任意调整(MySQL的查询优化器会自动调整where子句的条件顺序以使用适合的索引)。

  6. =和in可以乱序,比如a = 1 and b = 2 and c = 3 建立(a,b,c)索引可以任意顺序,mysql的查询优化器会帮你优化成索引可以识别的形式。

  7. 索引列不能参与计算,保持列“干净”,比如FROM_UNIXTIME(create_time) = ’2014-05-29’就不能使用到索引,原因很简单,b+树中存的都是数据表中的字段值,但进行检索时,需要把所有元素都应用函数才能比较,显然成本太大。所以语句应该写成create_time = UNIX_TIMESTAMP(’2014-05-29’);

举例:

表table有字段(A,B,C,D),其中主索引(A,B,C),辅助索引(D)。

情况一:全列匹配

使用A,B,C进行=或者in的查询时,主索引完全匹配,索引有效。(理论上,索引对条件的顺序敏感,但是MySQL的查询优化器会自动调整where子句的条件顺序以使用适合的索引,所以使用A,C,B后者C,B,A的顺序进行查询,效果是一样的)

情况二:最左前列匹配

使用A或者A和B的组合条件(必须含A)查询,可以用到索引

情况三:查询条件用到了索引中列的精确匹配,但是中间某个条件未提供

使用A和C查询,只有A索引生效。这种情况下,如果B列区分度较小,可以使用填坑的方法使C索引生效,A= and C= and B in (B的所有可能值)

情况四:查询条件没有指定第一列

使用B,B和C等条件查询,这时候索引不生效

情况五:匹配某字段的前缀字符串

A=’hello%’,只要通配符%不出现在开头,索引就生效

情况六:范围查询

范围列可以用到索引,但是范围列后面的列无法用到索引。另外,索引最多用于一个范围列,如果查询条件中有两个范围列则无法全用到索引。(注意between的情况很特殊,有兴趣的童鞋可以自己研究一下。)

情况七:字段用到表达式

A= and B-1=100,只有A索引生效;A= and B=100+1,AB索引都会生效

七、其他

索引原理以及索引的优化,这篇文章只涉及到其中一小部分,比如除了B树索引外很多存储引擎还支持哈希索引等,这篇文章并没有谈到。后面如果可以,希望能跟大家再深入探讨索引的各个方面。

 

参考

B树、B-树、B+树、B*树. http://www.cnblogs.com/oldhorse/archive/2009/11/16/1604009.html

MySQL索引背后的数据结构及算法原理. http://blog.codinglabs.org/articles/theory-of-mysql-index.html

数据库索引工作原理. http://www.cnblogs.com/oldhorse/archive/2009/11/16/1604009.html



是时候关注一个只分享干货的公众号了

长按二维码 关注我们

JAVA北京(java_bj)


 
Java北京 更多文章 万亿级调用系统:微信序列号生成器架构设计及演变 为什么大型网站前端使用 PHP 后台逻辑用 Java? CAS集群解决方案 一种大批量数据(文件解析)的处理方案 京东618:多中心交易平台系统高压下的高可用性
猜您喜欢 这样沟通,你会更很容易得到你想要的! 阿里云ecs上用nginx+uwsgi搭建flask运行环境 Docker基础技术:AUFS 别和一种语言厮守终生:为工作正确选择编程语言 Alamofire网络库进阶教程