MS 面试回顾

项目

感觉所有面试官都对ElasticSearch不了解，对ANTLR也没什么兴趣，问的大多是项目的背景，有一个问题感觉挺有意义但是我没有回答好：ES的index和MySQL的index有什么区别？底层各用到什么数据结构？
整理回答：
MySQL的索引底层用到的数据结构是B+树，B+树与B树相比，主要有以下两个不同：

1. B 树一个节点里存的是数据，而 B+树存储的是索引（地址），B 树里一个节点存不了很多个数据，但是 B+树一个节点能存很多索引，B+树叶子节点存所有的数据。
2. B+树的叶子节点存放数据，并用一个链表串联起来，便于范围查找。

在MySQL中，索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的，MyISAM和InnoDB两个存储引擎的索引都是使用B+树这个数据结构，区别在于MyISAM是非聚集索引，叶子节点存储的是数据的地址，而InnoDB是聚集索引，主键对应的B+树的叶子节点存储的是数据，而其他索引B+树的节点存储的是主键值。在查询非主键索引时，会先查询非主键索引拿到对应的主键值，然后查询主键索引拿到数据。

ElasticSearch通过 Lucene 的倒排索引技术实现比关系型数据库更快的过滤。对于一个字段，我们在分词后可以为每个term建立posting list，例如包含“apple”这个term的文档id为[1,3,5]。通过对term进行排序得到term dictionary，我们可以实现快速查找。但是term dictionary可能很大，可能无法放到内存中，于是就有了 term index。term index 是一棵 Trie 树，term index 有点像一本字典的大的章节表，通过 term index 可以快速地定位到 term dictionary 的某个 offset，然后从这个位置再往后顺序查找。

es索引.jpeg

MySQL和ElasticSearch 对比起来，MySQL 只有 term dictionary 这一层，以 B+ 树的方式存储在磁盘上的。检索一个 term 需要若干次的磁盘 的random access 操作。而 Lucene 在 term dictionary 的基础上添加了 term index 来加速检索，term index 以Trie树的形式缓存在内存中。从 term index 查到对应的 term dictionary 的 block 位置之后，再去磁盘上找 term，大大减少了磁盘的 random access 次数。

参考资料：

• 深入理解 Mysql 索引底层原理
• 数据库索引实现原理
• 时间序列数据库的秘密 (2)——索引

算法题

其实1，2，3面的算法题都不难，全是二叉树，但是没休息好，感觉头脑很懵，而且第一道算法题没做好，后面就全程有点飘。
总结经验：

1. 前一天休息好，早上不能起太早。
2. 一道题没做好后面也要抓紧调整心态。
3. 刷题要争取bug free，不能交上去看有什么错再改。
4. 写测试用例

面到的题：

1. 二叉树，每个节点有指向parent的指针，给定二叉树的root以及一个节点node，求中序遍历时node的下一个节点。这个题在写测试用例的时候，可以只构造一颗大树，求不同node的下一个节点，这样不用构造多棵树。
2. 二叉搜索树删除一个节点，返回操作后的二叉树（要求还是二叉搜索树）。
3. 二叉树找最近的公共节点。
4. 两个排序数组和的第K大。没做出来，参考博文

Java基础

Java的深拷贝怎么做？

1. 重载clone()方法
2. 序列化反序列化的方法

设计模式

1. 写一个单例模式

2. 装饰者模式是什么，写一个demo，装饰者模式与责任链模式的区别是什么？

   
   装饰者模式
   责任链模式