think-about-data-structure

为什么有数据结构的问题就是数据本来是无序和杂乱的
怎么在保存的时候方便后续更加方便查询和分析
如果是像记事本和word这种的确是可以使用单考虑到大量的数据就要考虑效率和成本

最后就发现了很多方法

  • 内存保存
  • 基于机械硬盘保存附以数据结构
  • 混合内存和硬盘保存包括数据的生命周期来实现

内存保存

redis,Cassandra,Neo4j 等将数据保存在内存中实现快速存储,同时还提供数据的持久化,和过期时间,同时包括其他的有效特性

磁盘保存

  1. 二分查找: 将文件数据有序保存,使用二分查找来完成特定key的查找。
  2. 哈希:用哈希将数据分割为不同的bucket
  3. B+树:使用B+树 或者 ISAM 等方法,可以减少外部文件的读取
  4. 外部文件: 将数据保存为日志,并创建一个hash或者查找树映射相应的文件。

basic lsm

基于硬盘的保存就要优先考虑磁盘原理,磁盘的探测器读取磁道的数据,所以数据是顺序读写的,且会预读取数据到内存,目前很多开发的分布式服务都基于此设计为(LSM Log Structured-Merge Tree) 包括kafka, hbase 等尽量避免顺序读写

b+数这类设计目标提高数据的查询的效率,在数据保存的时候将数据建议归类以树状的结构排列,同时在包括叶子节点和根节点来实现快速找对数据节点

通常数据库还有一个方式 WAL(writte ahaead log) 即写数据之前会先累积数据后在保存在

现在常见的数据保存结构有哪些

树状结构 b数,b+树,b-树

线性 lsm结构 数据保存读写会累积不是覆盖这种

数据库索引常见,b-tree,hash,gist,gin,sp-gist,brin

方便查询

方便读写

B-Tree 索引是 MySQL 数据库中使用最为频繁的索引类型,除了 Archive 存储引擎之外的其他所有的存储引擎都支持 B-Tree 索引。不仅仅在 MySQL 中是如此,实际上在其他的很多数据库管理系统中B-Tree 索引也同样是作为最主要的索引类型,这主要是因为B-Tree 索引的存储结构在数据库的数据检索中有非常优异的表现。
一般来说, MySQL 中的 B-Tree 索引的物理文件大多都是以 Balance Tree 的结构来存储的,也就是所有实际需要的数据都存放于 Tree 的 Leaf Node ,而且到任何一个 Leaf Node 的最短路径的长度都是完全相同的,所以我们大家都称之为 B-Tree 索引当然,可能各种数据库(或 MySQL 的各种存储引擎)在存放自己的 B-Tree 索引的时候会对存储结构稍作改造。如 Innodb 存储引擎的 B-Tree 索引实际使用的存储结构实际上是 B+Tree ,也就是在 B-Tree 数据结构的基础上做了很小的改造,在每一个Leaf Node (叶子节点)上面出了存放索引键的相关信息之外,还存储了指向与该 Leaf Node 相邻的后一个 LeafNode 的指针信息,这主要是为了加快检索多个相邻 Leaf Node 的效率考虑。
B+树是一个平衡的多叉树,从根节点到每个叶子节点的高度差值不超过1,而且同层级的节点间有指针相互链接。
在B+树上的常规检索,从根节点到叶子节点的搜索效率基本相当,不会出现大幅波动,而且基于索引的顺序扫描时,也可以利用双向指针快速左右移动,效率非常高。
因此,B+树索引被广泛应用于数据库、文件系统等场景。顺便说一下,xfs文件系统比ext3/ext4效率高很多的原因之一就是,它的文件及目录索引结构全部采用B+树索引,而ext3/ext4的文件目录结构则采用Linked list, hashed B-tree、Extents/Bitmap等索引数据结构,因此在高I/O压力下,其IOPS能力不如xfs。

所以使用

混合内存和硬盘保存包括数据的生命周期来实现

代表程序为 elasticsearch

数据过来会被建立索引保存在内存中后面会被保存在磁盘,数据的生命周期为hot warm cold delete

阶段 / action 优先级设置 取消跟随 滚动索引 分片分配 只读 强制段合并 收缩索引 冻结索引 删除
hot × × × × × ×
warm × × ×
cold × × × × ×
delete × × × × × × × ×