有4点：
1，时间复杂度为O(1)的磁盘访问能力。以时间复杂度O(1)的方式提供消息持久化能力，即使对TB以上的数据也能保证常数时间的访问性能。
思考一下，这个是如何实现的？
数组的时间复杂度是什么？
链表的时间复杂度是什么？
2，高吞吐率。Kafka可以提供单机每秒10万次的消息处理能力。
3，支持Kafka server间的消息分区存储，分布式消费，partition内有序。
4，同时支持数据离线处理和数据实时处理。
一，Kafka为什么能提供时间复杂度为O(1)的磁盘访问能力？
概括来说，有以下三点：
1，磁盘线性写入，或者从Kafka应用程序的角度来说是消息顺序追加。
怎么理解呢？什么是磁盘线性写入？什么是消息顺序追加？
磁盘的读写分为随机读写和线性读写。线性读写的效率比随机读写快6000倍。Kafka在设计时采用了文件追加的方式来写入消息，即只能在日志文件的尾部追加新的消息，并且不允许修改已经写入的消息。这样就可以利用磁盘的线性读写来提高磁盘访问速度。
2，磁盘页缓存
什么是页缓存？
页缓存是磁盘缓存。
页缓存是操作系统实现的磁盘缓存。
页缓存的目的是为了减少对磁盘的IO操作。
具体来说就是把磁盘的数据缓存到内存中，把对磁盘的访问变成对内存的访问。Kafka中大量使用了页缓存，这是Kafka实现高吞吐的关键因素之一。
3，零拷贝
什么是零拷贝？
零拷贝是一种避免CPU将数据从一块存储拷贝到另外一块存储的技术。零拷贝可以有效的改善数据传输的性能，在内核驱动程序处理IO数据的时候，零拷贝技术可以在某种程度上减少不必要的CPU拷贝操作。
接下来我们分析一下数组的时间复杂度。
数组根据下标随机访问的时间复杂度是O(1)，数组中查询某个元素的时间复杂度是O(log n)。
为什么呢？
数据的特性：数据码成一排进行存放，每一个数据对应一个索引，支持随机访问，初始化必须指定大小。
注意：数组索引可以有意义也可没有意义，但最好应用于索引有意义的情况因为其支持随机访问的特性，根据索引查找对应数据所用的时间复杂度为O(1)。
二，动态数组时间复杂度分析
动态数组
由于很多时候我们开始的时候不知道需要创建多大长度的数组，此时可以在创建的时候创建一个很大的静态数据，但这样做会耗费不必要的存储空间，也并不能绝对保证元素个数不超过数组容量。此时动态数组的出现就解决了这个问题
动态数组底层使用的是静态数组实现的大概实现思路如下：
首先创建一个固定容量的静态数组，在执行插入元素是超过当前数组预定义的最大值时，重新创建一个更大容量的数组，将小容量数组数据拷贝到新数组中，接下来的插入操作就使用我们新创建的这个数组。删除元素也同理，删除元素后当前元素总数小于数组容量的一半（实际并不是一半举例而已）时重新创建一个小容量数组，将旧数组内容拷贝过来，之后就使用新创建的这个数组，这么做既不会浪费太多空间也能保证了可以存储足够多的数组。
在Java中的ArrayList就是一个动态数组，的实现方式大概是相同的,扩容过程需要调用底层System.arraycopy()方法进行大量的数组复制操作；在删除元素时并不会减少数组的容量（如果需要缩小数组容量，可以调用trimToSize()方法）；在查找元素时要遍历数组，对于非null的元素采取equals的方式寻找。
什么是时间复杂度：
常见的时间复杂度有：O(1),O(n),O(lgn),O(nlogn),O(n^2)
大O描述的是算法的运行时间和输入数据之间的关系。
动态数组时间复杂度分析：
添加元素：O(n)
向索引为index的地方添加元素，那么index之后的元素都需要像后移动，所以向数组头添加元素需要进行n次操作即O(n)，向末尾只需进行一次操作即O(1)，通过概率论知识计算出每次添平均需要进行n/2次操作，所以时间复杂度为O(n/2)省略常数1/2，添加操作的时间复杂度就为O(n)。
但是有的胸弟就发现了向末尾添加元素不一定时间复杂度为O(1)啊，因为可能进行扩容，此时就用到了上面没说的均摊时间复杂度，扩容这个操作不是每次都触发的，例如容量为10，一直添加元素在第10次的时候才触发了扩容，此时添加10个元素进行了20次操作， 均摊给每一次操作时间复杂度为O(2)，O(2)就等于O(1)，这就叫做均摊时间复杂度。
此时又有胸弟找茬了，如果在元素占满数组容量时进行扩容到原来容量的2倍，在元素个数小于数组容量一半时进行缩容为当前容量一半，那么如果总是在动态数组末尾添加一个元素，再删除一个元素，重复这两个步骤，不断的进行扩容和缩容，此时时间复杂度就为O(n)了，这就叫做复杂度震荡，但这个问题是可以解决的，只需要在元素个数小于容量的1/4时候才进行缩容为当前容量的一半。一个好的算法应该尽量避免复杂度震荡。
删除元素：O(n) 同添加相同思路
查询元素：O(1) 每次只需根据索引进行一次操作
总结：由于ArrayList对元素的增加和删除都会引起数组的内存分配空间动态发生变化。因此，对其进行插入和删除速度较慢，但检索速度是很快的。
三，有序数组和无序数组
有序数组和无序数组的概念，什么是有序数组，什么是无序数组？有序数组的增删改查的时间复杂度是什么？无序数组的增删改查的时间复杂度是什么？
四，二分法和二叉树
二分法和二叉树，这2个概念不要搞混了？
查找算法中的“二分法”是这样定义的：
给定N个从小到大排好序的整数序列List[]，以及某待查找整数X，我们的目标是找到X在List中的下标。即若有List[i]=X，则返回i；否则返回-1表示没有找到。
二分法是先找到序列的中点List[M]，与X进行比较，若相等则返回中点下标；否则，若List[M]>X，则在左边的子系列中查找X；若List[M]<X，则在右边的子系列中查找X。
什么是二叉树呢？
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^（i − 1）个结点;深度为k的二叉树至多有2^k − 1个结点;对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2 + 1。二叉树算法常被用于实现二叉查找树和二叉堆。
网友评论