-前言-
Mysql作为跨语言web开发基本都在用的关系型数据库,在面试时,%都会遇到.简历上都会写熟悉mysql使用,聊到mysql聊到innodb,B+Tree就不得不提.
-B+Tree-
1、数据结构BTree指的是BalanceTree，也就是平衡树。平衡树是一颗查找树，并且所有叶子节点位于同一层。
B+Tree是基于BTree和叶子节点顺序访问指针进行实现，它具有BTree的平衡性，并且通过顺序访问指针来提高区间查询的性能。
在B+Tree中，一个节点中的key从左到右非递减排列，如果某个指针的左右相邻key分别是keyi和keyi+1，且不为null，则该指针指向节点的所有key大于等于keyi且小于等于keyi+1。
2、操作进行查找操作时，首先在根节点进行二分查找，找到一个key所在的指针，然后递归地在指针所指向的节点进行查找。直到查找到叶子节点，然后在叶子节点上进行二分查找，找出key所对应的data。
插入删除操作会破坏平衡树的平衡性，因此在进行插入删除操作之后，需要对树进行分裂、合并、旋转等操作来维护平衡性
3、与红黑树的比较红黑树等平衡树也可以用来实现索引，但是文件系统及数据库系统普遍采用B+Tree作为索引结构，这是因为使用B+树访问磁盘数据有更高的性能。
（一）B+树有更低的树高
平衡树的树高O(h)=O(logdN)，其中d为每个节点的高度。红黑树的出度为2，而B+Tree的出度一般都非常大，所以红黑树的树高h很明显比B+Tree大非常多。
（二）磁盘访问原理
操作系统一般将内存和磁盘分割成固定大小的块，每一块称为一页，内存与磁盘以页为单位交换数据。数据库系统将索引的一个节点的大小设置为页的大小，使得一次I/O就能完全载入一个节点。
如果数据不在同一个磁盘块上，那么通常需要移动制动手臂进行寻道，而制动手臂因为其物理结构导致了移动效率低下，从而增加磁盘数据读取时间。B+树相对于红黑树有更低的树高，进行寻道的次数与树高成正比，在同一个磁盘块上进行访问只需要很短的磁盘旋转时间，所以B+树更适合磁盘数据的读取。
（三）磁盘预读特性
为了减少磁盘I/O操作，磁盘往往不是严格按需读取，而是每次都会预读。预读过程中，磁盘进行顺序读取，顺序读取不需要进行磁盘寻道，并且只需要很短的磁盘旋转时间，速度会非常快。并且可以利用预读特性，相邻的节点也能够被预先载入
总结:回答这个问题,有这几个重点
1.B+Tree的特性
2.对操作系统磁盘预读的使用,叶子节点的顺序性.
3.尽量把B+Tree的简化版的图画出来有图有真相.
我是南哥，祝各位早日找到满意的Offer,感谢各位道友的：点赞、在看
预览时标签不可点收录于话题#个上一篇下一篇.1.14
智造核芯云实践·day3
ApacheIoTDB
.1.14
背景介绍/BackGround/
工业界的需求与IoTDB产生的背景
大数据曾经是热点话题，而大数据的收集与处理离不开数据库。工业物联网的数据和一般的大数据形式与对性能的要求不尽相同，对于数据库的要求也会更高，IoTDB在这种背景中应运而生。
工业物联网数据是蕴含丰富工业语义信息的时间序列数据，是按照时间观测的工业设备物理量在信息系统中的数字化记录。
工业物联网数据体量庞大，举个简单的例子，一台列车上有多测点，每个传感器每ms采样一次，一个城市同时运营的列车数量超过，一天下来采样数据就会超过亿个数据点，占据约GB的存储空间，可想而知其数据量是多么庞大，因此要求数据库能够高效而紧凑的存储数据。
工业物联网数据的数据总吞吐量很大，因此需要数据库能够高效写入与读取，否则面对庞大的数据分析起来会极其消耗时间。
工业物联网数据还有一个特点是产生速度极快并且不间断，因此需要保证数据可以全时全量的存储，这就给数据库带来了更大的挑战。
而有了ApacheIoTDB，上述问题都迎刃而解。
ApacheIoTDB
ApacheIoTDB始于中国高校、历练于工业用户、成长成熟于开源社区。
ApacheIoTDB在年11月进入Apache孵化器，在年9月毕业成为Apache顶级项目。
目前，ApacheIoTDB能够做到工业领域千万条量级的时间序列管理，单节点万亿数据点的管理，拥有单节点每秒千万点的写入性能和单节点数十TB级时间序列数据管理，用户已经覆盖德国、美国、中国一批工业互联网厂商和智能制造厂商。
嘉宾介绍
孙泽嵩，清华大学软件学院19级硕士生，目前在信息所大数据系统软件国家工程实验室从事研究和开发工作，研究方向为大数据与时序数据库。现担任ApacheIoTDB项目
A浏览器结构模型
Chromium主要有Browser，Render，GPU等进程，还有插件进程没在下图表示。由于Chromium工程设计的灵活性，提供多种选择，所以这几个可以部分为独立进程，也可以不设置为独立进程。当然这种灵活性本身也增加了不少工程量。
Chroimium跨进程模型
1、Browser进程
页面显示，tab页面管理，用户交互，下载管理等。
2、Render进程
渲染进程，根据不同情况可以为一个或者多个，
Processpersiteinstance：
每一个页面都创建一个独立的Render进程，不管这些页面是否来自于同一域。
Processpersite：
属于同一个域的页面共享同一个进程，而不同属一个域的页面则分属不同的进程。
Processpertab：
Chromium每个标签页都是独立进程
Singleprocess：
该类型的含义是，Chromium不单独为页面创建任何独立进程，所有渲染工作都在Browser进程中进行，它们是Browser进程中的多个线程。
3、GPU进程
4、NPAPI插件进程
B不同平台之间的跨平台问题
Chromium由Google开源并维护，代码规模异常庞大，跨多个平台，包括Mac系统，Linux系统，Windows系统，iOS系统（其中有部分和maccocoa共用）以及Google自己的Android系统。Chomium维护了多个平台和UI的一致性，这也是导致他异常复杂的原因之一了。
我们可以参考一下Chromium跨平台的一些做法，这些做法让代码结构易于维护和保持一致性。
一、就是利用后缀命名的方式：
Mac文件用_mac，其中涉及UI（cocoa）部分用_cocoa。MacCocoa:chrome/browser/ui/cocoa
Linux文件用_linux后缀，其中GTK专有的部分用_gtk，其他专有部分用_x。LinuxGTK:chrome/browser/ui/gtk
Windows系统用_win后缀。
iOS用_ios后缀，不过iOS部分使用_mac。
各平台（MaciOSLinux）用_posix后缀share文件。
浏览器前端代码分别由各自的平台自己的目录下面。
二、#ifdef大法
refC++语言。待续C++部分
三、impl大法
refC++语言。头文件h文件中，可以用#ifdef区别不太的平台，如果比较大的实现部分可以用implenataion的方式来分离。
在base目录下就有不少的例子，其中waitable_event.h中，基于不同平台的情况定义通用API。其中给不同的平台定义了不同的实现，当然，如果需要定义一些通用的东西还是需要增加waitable_event.cc的实现的。
和waitable_event有关的目录
另外，单独的几乎没有共用部分的代码可以使用xx_xx_win这样的方式来命名，其中的类Xx_Xx_Win。
C浏览器的启动过程代码
浏览器启动部分代码目录：
启动入口目录
Windows
在Windows系统上，构建一个dll来启动WinMain入口。。。。
Mac
在Mac上打包成一个Framework以及一个可执行文件，这二者可链接在一起。通过main函数启动ChromeMain来启动。另外还有一个启动入口位于/src/chrome/app_shim/chrome_main_app_mode_mac.mm。这个入口同样调用ChromeMain函数
Linux
由于沙盒的因素，可以启动一个子进程，确保子进程本身不会再进main函数。最后也同样是调用ChromeMain函数。
D渲染模型
Chromium及其庞大复杂，其中webkit/blink渲染页面主要包括如下几个步骤：
1、解析成DOM
----每一个HTML节点都可以对应到DOM树种的一个节点Node。其中顶层根节点应该就是Document节点。
2、将DOM转成RenderObject树
-----DOM树种的每个可视节点都对应到Render树的每个节点，并且通过GraphicsContext绘制。GraphicsContext可以wrap一些skiaopengl等，关于GraphicsContext待续。
3、转成RenderLayer
----每一个RenderObject节点都可以通过祖先节点直接或者间接的对应到RenderLayer节点。有共同坐标系空间的RenderObject都在一个RenderLayer。
符合一些条件可以为部分的RenderObeject创建一个RenderLayer，定义RenderBoxModelObject::requiresLayer()
DOM树的Document节点对应的RenderView节点。DOM树中的Document的子女节点，也就是HTML节点对应的RenderBlock节点。显式的指定CSS位置的RenderObject节点。有透明效果的RenderObject节点。节点有溢出（Overflow）、alpha或者反射等效果的RenderObject节点。使用Canvas2D和3D(WebGL)技术的RenderObject节点。Video节点对应的RenderObject节点。
*页面的根节点
*显示的有CSS指定的位置属性（相对绝对or转换）。
*透明节点
*有溢出alpha或者反射效果的节点
*有一个CSS过滤器
*可以有3D(WebGL)或者加速2DContext对应到canvas节点
*对应到video节点
所以RenderObject和RenderLayer不是一一对应的关系。并且RenderLayer本身也是树形结构。
*从RenderLayers到GraphicsLayers**
为了利用Compositor，部分RenderLayer有自己的BackingSurface。所有的RenderLayer都有都使用自己的graphicLayer或者自己最近祖先的GraphicLayer。这点和RenderObject和RenderLayer关系类似。
每个GraphicsLayer都有一个GraphicsContext供关联的RenderLayers绘制。合成器最终负责在随后的合成过程中将GraphicsContexts的位图输出一起合并到最终的屏幕图像中。
从理论上讲，每个单独的RenderLayer都可以将其自身绘制到单独的支持表面上，但实际上在内存方面（尤其是VRAM）这可能非常浪费。在当前的Blink实现中，必须满足以下条件之一才能使RenderLayer获得其自己的合成层(/third_party/blink/renderer/platform/graphics/