JAVA程序猿3000问第1日

JAVA程序猿3000问第1日

第一问 介绍一下b/b-/b+树
第二问 Mysql不显示声明事务,3条select的事务会是什么样的?
第三问 介绍一下乐观锁和悲观锁。
第四问 数据库索引在哪些情况下会失效?
第五问 在生产上哪些情况会发生重量级的full gc?如何调优?

第一问 介绍一下b/b-/b+/b*树

首先B-tree树即B树,B即Balanced,平衡的意思。因为B树的原英文名称为B-tree,而国内很多人喜欢把B-tree译作B-树,其实,这是个非常不好的直译,很容易让人产生误解。如人们可能会以为B-树是一种树,而B树又是另一种树。而事实上是,B-tree就是指的B树。特此说明。

b树

b树的是一种多路搜索树(不是二叉树),可以先看看二叉搜索树的概念,即左子节点的值小于父节点,右子节点的值大于父节点:
二叉搜索树
二叉搜索树每个节点最多有两个子节点,多路搜索树每个节点可以有任意M(M>2)个子节点,每个结点存放至少M/2-1(取上整)和至多M-1个关键字;(至少2个关键字1)

b树的具体定义:

  1. 定义任意非叶子结点最多只有M个儿子;且M>2;
  2. 根结点的儿子数为[2, M];
  3. 除根结点以外的非叶子结点的儿子数为[M/2, M];
  4. 每个结点存放至少M/2-1(取上整)和至多M-1个关键字;(至少2个关键字)
  5. 非叶子结点的关键字个数=指向儿子的指针个数-1;
  6. 非叶子结点的关键字:K[1], K[2], …, K[M-1];且K[i] < K[i+1];
  7. 非叶子结点的指针:P[1], P[2], …, P[M];其中P[1]指向关键字小于K[1]的子树,P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1], K[i])的子树;
  8. 所有叶子结点位于同一层;
    M=3的情况

b树的特点

  1. 关键字集合分布在整颗树中;
  2. 任何一个关键字出现且只出现在一个结点中;
  3. 搜索有可能在非叶子结点结束;
  4. 其搜索性能等价于在关键字全集内做一次二分查找;
  5. 自动层次控制

b树性能

由于限制了除根结点以外的非叶子结点,至少含有M/2个儿子,确保了结点的至少利用率,其最低搜索性能为:
推导过程
其中,M为设定的非叶子结点最多子树个数,N为关键字总数;
所以B-树的性能总是等价于二分查找(与M值无关),也就没有B树平衡的问题;
由于M/2的限制,在插入结点时,如果结点已满,需要将结点分裂为两个各占M/2的结点;删除结点时,需将两个不足M/2的兄弟结点合并

b+树

b+树是b树的一种变种,b+树定义和b树基本一致,只是所有的关键字都会在叶子节点出现。

b+树定义

  1. 非叶子结点的子树指针与关键字个数相同;
  2. 非叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1])的子树(B-树是开区间);
  3. 为所有叶子结点增加一个链指针;
  4. 所有关键字都在叶子结点出现;
    M=3的情况

b+树特性

  1. 所有关键字都出现在叶子结点的链表中(稠密索引),且链表中的关键字恰好是有序的;
  2. 不可能在非叶子结点命中;
  3. 非叶子结点相当于是叶子结点的索引(稀疏索引),叶子结点相当于是存储(关键字)数据的数据层;
  4. 更适合文件索引系统;

b*树

是B+树的变体,在B+树的非根和非叶子结点再增加指向兄弟的指针,所以在分配新节点的效率上会更高,出现有空余的节点概率更低,空间利用率更高
b*树

  • B+树的分裂:当一个结点满时,分配一个新的结点,并将原结点中1/2的数据复制到新结点,最后在父结点中增加新结点的指针;B+树的分裂只影响原结点和父结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针;
  • B*树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了);如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针;

第二问 Mysql不显示声明事务,3条select的事务会是什么样的?

Mysql默认认autocommit,mysql会把每一条语句都当成一次事务开启并提交。

第三问 介绍一下乐观锁和悲观锁。

  • 悲观锁是指假设并发更新冲突会发生,所以不管冲突是否真的发生,都会使用锁机制。如java的sycronized等锁机制

  • 乐观锁顾名思义,就是很乐观,每次去拿数据的时候都认为别人不会修改,所以不会上锁,但是在更新的时候会判断一下在此期间别人有没有去更新这个数据,可以使用版本号等机制。乐观锁适用于多读的应用类型,这样可以提高吞吐量。如java的AQS机制

第四问 数据库索引在哪些情况下会失效?

  1. 如果条件中有or,即使其中有条件带索引也不会使用(要想使用or,又想让索引生效,只能将or条件中的每个列都加上索引)
  2. 对于多列索引(复合索引),不是使用的第一部分(复合索引的第一个字段),则不会使用索引
  3. like查询是以%开头
  4. 如果列类型是字符串,那一定要在条件中将数据使用引号引用起来,否则不使用索引
  5. 如果mysql认为全表扫面要比使用索引快,则不使用索引。如:表里只有一条数据。

    查看索引的使用情况:show status like ‘Handler_read%’;
    注意:
    handler_read_key:这个值越高越好,越高表示使用索引查询到的次数
    handler_read_rnd_next:这个值越高,说明查询低效

第五问 在生产上哪些情况会发生重量级的full gc?如何调优?

  1. minor gc很频繁,但时间短所以问题不大,触发原因基本都是申请空间失败。
  2. 偶尔有System.gc(),时间大概1分钟。代码中没有显式调用,基本确定是监控程序RMI访问触发的。可以加参数禁用 -XX:+DisableExplicitGC 。
  3. 时常有promotion failed,即在minor gc时年轻代的存活区空间不足而进入老年代,老年代又空间不足而触发full gc。时间大概3分钟。解决思路一种是增大存活区,一种则相反是去掉存活区增大老年代。相关参数一般有:
    -XX:SurvivorRatio=32 存活区除以伊甸区的比率,存活区有from和to两个,所以这里的意思是单个存活区占年轻代的1/34;
    -XX:OldSize=60M 老年代大小;
    -XX:MaxTenuringThreshold=15 即多少次minor gc后存活的年轻代对象会晋升老年代。
  4. 经常有concurrent mode failure,即CMS执行过程中老年代空间不足,这时会变成Serial Old收集器导致更长时间的停顿。时间大概5分钟。其中引发这一问题的情况可能是浮动垃圾太多、可能是CMS收集器本身也占用堆空间、也可能是老年代太多碎片,但都是CMS收集器的特性导致的。相关配置一般有:
    -XX:CMSInitiatingOccupancyFraction=80 即老年代满80%时触发CMS(full gc),调高则full gc相对减少,调低则full gc处理得比较快;
    -XX:UseCMSCompactAtFullCollection 或 -XX:CMSFullGCsBeforeCompaction=5 即full gc前或后做碎片整理。

ps : 这篇文章是一个新系列,每天记录5道java程序猿常见面试题,当记录满3000问之后相信会变得更强。がんばります!

参考

https://blog.csdn.net/u013411246/article/details/81088914
https://blog.csdn.net/a724888/article/details/81389605
https://www.cnblogs.com/itsharehome/p/4972948.html

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×