精华内容
下载资源
问答
  • MySQL数据存储结构

    万次阅读 2017-07-15 17:36:26
    2、不支持聚簇索引:数据不能保存在索引中,单独存储 存储结构数据保存在连续的内存中,如果没有行号,还会隐式加上行号,结构如下图: 主键索引:主键列值+行号 二次索引:索引列值+行号,和主键索引没...

    第一部分:存储引擎及存储结构

    记住:每个索引就是一个B-tree
    Mysql最重要的两个存储引擎是:
    MyISAM:
    1、不支持事物:无法回滚
    因此,无法在崩溃后安全恢复
    2、不支持聚簇索引(数据存储方式不同):数据不能保存在索引中,单独存储
    3、不支持行锁:
    4、select count(*),不需要扫描整个表,数值直接获取
    存储结构:
    数据保存在连续的内存中,如果没有行号,还会隐式加上行号,结构如下图:
    这里写图片描述
    主键索引:主键列值+行号
    这里写图片描述
    二次索引:索引列值+行号,和主键索引没多大区别
    这里写图片描述
    Inodb:
    1、支持事物:崩溃后可以安全恢复
    2、支持聚簇,只能有一个聚簇索引,一般是主键
    3、支持行锁
    4、select count(*) 要扫描整个表

    存储结构:
    数据是存储在主键索引里面的,记住,每个索引就是一个B-tree
    主键列值
    事物ID
    回滚指针
    其他列值(所以查到主键索引就能找到整行的数据)
    这里写图片描述
    二次索引:
    索引列值+主键列值
    所以按照索引查找可以先找到主键列,再去回表找到主键索引,返回整行数据
    这里写图片描述

    第二部分:B-tree与哈希索引的区别

    B-tree的索引是按照顺序存储的,所以,如果按照B-tree索引,可以直接返回,带顺序的数据,但这个数据只是该索引列含有的信息。因此是顺序I/O
    适用于:
    精确匹配
    范围匹配
    最左匹配

    Hash索引:
    索引列值的哈希值+数据行指针:因此找到后还需要根据指针去找数据,造成随机I/O
    适合:
    精确匹配
    不适合:
    模糊匹配
    范围匹配
    不能排序
    摘抄其他人的的总结:
    1、hash索引仅满足“=”、“IN”和“<=>”查询,不能使用范围查询
    因为hash索引比较的是经常hash运算之后的hash值,因此只能进行等值的过滤,不能基于范围的查找,因为经过hash算法处理后的hash值的大小关系,并不能保证与处理前的hash大小关系对应。
    2、hash索引无法被用来进行数据的排序操作
    由于hash索引中存放的都是经过hash计算之后的值,而hash值的大小关系不一定与hash计算之前的值一样,所以数据库无法利用hash索引中的值进行排序操作。
    3、对于组合索引,Hash 索引在计算 Hash 值的时候是组合索引键合并后再一起计算 Hash 值,而不是单独计算 Hash 值,所以通过组合索引的前面一个或几个索引键进行查询的时候,Hash 索引也无法被利用。
    4、Hash 索引遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高。
    对于选择性比较低的索引键,如果创建 Hash 索引,那么将会存在大量记录指针信息存于同一个 Hash 值相关联。这样要定位某一条记录时就会非常麻烦,会浪费多次表数据的访问,而造成整体性能低下。

    总结:哈希适用在小范围的精确查找,在列数据很大,又不需要排序,不需要模糊查询,范围查询时有用

    展开全文
  • MYSQL INNODB数据存储结构

    万次阅读 多人点赞 2018-07-18 17:03:33
    所以先整理InnoDB的数据存储结构。 关键词:Pages, Extents, Segments, and Tablespaces 如何存储表 MySQL 使用 InnoDB 存储表时,会将表的定义和数据索引等信息分开存储,其中前者存储在 .frm 文件中,后者存储...

    一 序:

        在整理InnoDB存储引擎的索引的时候,发现B+树是离不开页面page的。所以先整理InnoDB的数据存储结构。

    关键词:Pages, Extents, Segments, and Tablespaces

    如何存储表

    MySQL 使用 InnoDB 存储表时,会将表的定义和数据索引等信息分开存储,其中前者存储在 .frm 文件中,后者存储在 .ibd 文件中,这一节就会对这两种不同的文件分别进行介绍。

    .frm

    无论在 MySQL 中选择了哪个存储引擎,所有的 MySQL 表都会在硬盘上创建一个 .frm 文件用来描述表的格式或者说定义; .frm 文件的格式在不同的平台上都是相同的。

    .ibd 文件
    InnoDB 中用于存储数据的文件总共有两个部分,一是系统表空间文件,包括 ibdata1、 ibdata2 等文件,其中存储了 InnoDB 系统信息和用户数据库表数据和索引,是所有表公用的。
    当打开 innodb_file_per_table 选项时, .ibd 文件就是每一个表独有的表空间,文件存储了当前表的数据和相关的索引数据。

    表空间

          innodb存储引擎在存储设计上模仿了Oracle的存储结构,其数据是按照表空间进行管理的。新建一个数据库时,innodb存储引擎会初始化一个名为ibdata1 的表空间文件,默认情况下,这个文件会存储所有表的数据,以及我们所熟知但看不到的系统表sys_tables、sys_columns、sys_indexes 、sys_fields等。此外,还会存储用来保证数据完整性的回滚段数据,当然这部分数据在新版本的MySQL中,已经可以通过参数来设置回滚段的存储位置了;

      

    看下官网的介绍:

    A data file that can hold data for one or more InnoDB tables and associated indexes.
    
    The system tablespace contains the InnoDB data dictionary, and prior to MySQL 5.6 holds all other InnoDB tables by default.
    
    The innodb_file_per_table option, enabled by default in MySQL 5.6 and higher, allows tables to be created in their own tablespaces. File-per-table tablespaces support features such as efficient storage of off-page columns, table compression, and transportable tablespaces. See Section 14.7.4, “InnoDB File-Per-Table Tablespaces” for details.

        innodb存储引擎的设计很灵活,可以通过参数innodb_file_per_table来设置,使得每一个表都对应一个自己的独立表空间文件,而不是存储到公共的ibdata1文件中。独立的表空间文件之存储对应表的B+树数据、索引和插入缓冲等信息,其余信息还是存储在默认表空间中。

        这个文件所存储的内容主要就是B+树(索引),一个表可以有多个索引,也就是在一个文件中,可以存储多个索引,而如果一个表没有索引的话,用来存储数据的被称为聚簇索引,也就是说这也是一个索引。最终的结论是,ibd文件存储的就是一个表的所有索引数据。 索引文件有段(segment),簇(extends)(有的文章翻译为区),页面(page)组成。

      关于行记录格式,单独整理一篇。

    二 段(segment)

          段是表空间文件中的主要组织结构,它是一个逻辑概念,用来管理物理文件,是构成索引、表、回滚段的基本元素。
         上图中显示了表空间是由各个段组成的,常见的段有数据段、索引段、回滚段等。InnoDB存储引擎表是索引组织的(index organized),因此数据即索引,索引即数据。那么数据段即为B+树的页节点(上图的leaf node segment),索引段即为B+树的非索引节点(上图的non-leaf node segment)。

       创建一个索引(B+树)时会同时创建两个段,分别是内节点段和叶子段,内节点段用来管理(存储)B+树非叶子(页面)的数据,叶子段用来管理(存储)B+树叶子节点的数据;也就是说,在索引数据量一直增长的过程中,所有新的存储空间的申请,都是从“段”这个概念中申请的。

      为了介绍索引为目的,所以不展开介绍回滚段等内容。

    三 区/簇(extents)

         段是个逻辑概念,innodb引入了簇的概念,在代码中被称为extent;

           簇是由64个连续的页组成的,每个页大小为16KB,即每个簇的大小为1MB。簇是构成段的基本元素,一个段由若干个簇构成。一个簇是物理上连续分配的一个段空间,每一个段至少会有一个簇,在创建一个段时会创建一个默认的簇。如果存储数据时,一个簇已经不足以放下更多的数据,此时需要从这个段中分配一个新的簇来存放新的数据。一个段所管理的空间大小是无限的,可以一直扩展下去,但是扩展的最小单位就是簇。

    四 页(page)

    InnoDB有页(page)的概念,可以理解为簇的细化。页是InnoDB磁盘管理的最小单位。

    常见的页类型有:
    数据页(B-tree Node)。
    Undo页(Undo Log Page)。
    系统页(System Page)。
    事务数据页(Transaction system Page)。
    插入缓冲位图页(Insert Buffer Bitmap)。
    插入缓冲空闲列表页(Insert Buffer Free List)。
    未压缩的二进制大对象页(Uncompressed BLOB Page)。
    压缩的二进制大对象页(Compressed BLOB Page)。

          在逻辑上(页面号都是从小到大连续的)及物理上都是连续的。在向表中插入数据时,如果一个页面已经被写完,系统会从当前簇中分配一个新的空闲页面处理使用,如果当前簇中的64个页面都被分配完,系统会从当前页面所在段中分配一个新的簇,然后再从这个簇中分配一个新的页面来使用;

    看下官网的介绍:

    Pages, Extents, Segments, and Tablespaces

    Each tablespace consists of database pages. Every tablespace in a MySQL instance has the same page size. By default, all tablespaces have a page size of 16KB; you can reduce the page size to 8KB or 4KB by specifying the innodb_page_size option when you create the MySQL instance. You can also increase the page size to 32KB or 64KB. For more information, refer to the innodb_page_sizedocumentation.

    The pages are grouped into extents of size 1MB for pages up to 16KB in size (64 consecutive 16KB pages, or 128 8KB pages, or 256 4KB pages). For a page size of 32KB, extent size is 2MB. For page size of 64KB, extent size is 4MB. The “files” inside a tablespace are called segments in InnoDB. (These segments are different from the rollback segment, which actually contains many tablespace segments.)

    When a segment grows inside the tablespace, InnoDB allocates the first 32 pages to it one at a time. After that, InnoDB starts to allocate whole extents to the segment. InnoDB can add up to 4 extents at a time to a large segment to ensure good sequentiality of data.

    Two segments are allocated for each index in InnoDB. One is for nonleaf nodes of the B-tree, the other is for the leaf nodes. Keeping the leaf nodes contiguous on disk enables better sequential I/O operations, because these leaf nodes contain the actual table data.

    Some pages in the tablespace contain bitmaps of other pages, and therefore a few extents in an InnoDB tablespace cannot be allocated to segments as a whole, but only as individual pages.

    五 组织结构

          这里在《MySQL运维内参》说的不是特别细: 一个表空间可以有多个文件,每个文件都有各自的编号,创建一个表空间时,至少有一个文件,这个文件被称为“0号文件”。一个文件是被切割为等长“默认16KB”的块,这个块通常被称为页面,那么在“0号文件”的第一个页面(page_no为0)中,存储了这个表空间中所有段簇也管理的入口,那么在这个页面存储的数据就是16KB,但通常会有页面头信息会占用一些空间,真正的管理信息数据是从页面偏移为fil_page_data(38)的位置开始的,这个位置存储了表空间的描述信息;

        淘宝的mysql给出了更详细:先看这个图,有个大概概念,再往下看。

    5.1 FSP_HDR PAGE

    数据文件的第一个Page类型为FIL_PAGE_TYPE_FSP_HDR,在创建一个新的表空间时进行初始化(fsp_header_init),该page同时用于跟踪随后的256个Extent(约256MB文件大小)的空间管理,所以每隔256MB就要创建一个类似的数据页,类型为FIL_PAGE_TYPE_XDES ,XDES Page除了文件头部外,其他都和FSP_HDR页具有相同的数据结构,可以称之为Extent描述页,每个Extent占用40个字节,一个XDES Page最多描述256个Extent。

    FSP_HDR页的头部使用FSP_HEADER_SIZE个字节来记录文件的相关信息,具体的包括:

    Macro bytes Desc
    FSP_SPACE_ID 4 该文件对应的space id
    FSP_NOT_USED 4 如其名,保留字节,当前未使用
    FSP_SIZE 4 当前表空间总的PAGE个数,扩展文件时需要更新该值(fsp_try_extend_data_file_with_pages
    FSP_FREE_LIMIT 4 当前尚未初始化的最小Page No。从该Page往后的都尚未加入到表空间的FREE LIST上。
    FSP_SPACE_FLAGS 4 当前表空间的FLAG信息,见下文
    FSP_FRAG_N_USED 4 FSP_FREE_FRAG链表上已被使用的Page数,用于快速计算该链表上可用空闲Page数
    FSP_FREE 16 当一个Extent中所有page都未被使用时,放到该链表上,可以用于随后的分配
    FSP_FREE_FRAG 16 FREE_FRAG链表的Base Node,通常这样的Extent中的Page可能归属于不同的segment,用于segment frag array page的分配(见下文)
    FSP_FULL_FRAG 16 Extent中所有的page都被使用掉时,会放到该链表上,当有Page从该Extent释放时,则移回FREE_FRAG链表
    FSP_SEG_ID 8 当前文件中最大Segment ID + 1,用于段分配时的seg id计数器
    FSP_SEG_INODES_FULL 16 已被完全用满的Inode Page链表
    FSP_SEG_INODES_FREE 16 至少存在一个空闲Inode Entry的Inode Page被放到该链表上

    簇或者分区(extent)是段的组成元素,在文件头使用FLAG描述了创建表信息,除此之外其他部分的数据结构和XDES PAGE都是相同的,使用连续数组的方式,每个XDES PAGE最多存储256个XDES Entry,每个Entry占用40个字节,描述64个Page(即一个Extent)。格式如下:

    Macro bytes Desc
    XDES_ID 8 如果该Extent归属某个segment的话,则记录其ID
    XDES_FLST_NODE 12(FLST_NODE_SIZE) 维持Extent链表的双向指针节点
    XDES_STATE 4 该Extent的状态信息,包括:XDES_FREE,XDES_FREE_FRAG,XDES_FULL_FRAG,XDES_FSEG,详解见下文
    XDES_BITMAP 16 总共16*8= 128个bit,用2个bit表示Extent中的一个page,一个bit表示该page是否是空闲的(XDES_FREE_BIT),另一个保留位,尚未使用(XDES_CLEAN_BIT)

    XDES_STATE表示该Extent的四种不同状态:

    Macro Desc
    XDES_FREE(1) 存在于FREE链表上
    XDES_FREE_FRAG(2) 存在于FREE_FRAG链表上
    XDES_FULL_FRAG(3) 存在于FULL_FRAG链表上
    XDES_FSEG(4) 该Extent归属于ID为XDES_ID记录的值的SEGMENT。

    通过XDES_STATE信息,我们只需要一个FLIST_NODE节点就可以维护每个Extent的信息,是处于全局表空间的链表上,还是某个btree segment的链表上。

    IBUF BITMAP PAGE 也就是page类型为FIL_PAGE_IBUF_BITMAP不展开,待单独整理。再看段的。

    5.2 INODE PAGE

    数据文件的第3个page的类型为FIL_PAGE_INODE,用于管理数据文件中的segement,每个索引占用2个segment,分别用于管理叶子节点和非叶子节点。每个inode页可以存储FSP_SEG_INODES_PER_PAGE(默认为85)个记录。

    Macro bits Desc
    FSEG_INODE_PAGE_NODE 12 INODE页的链表节点,记录前后Inode Page的位置,BaseNode记录在头Page的FSP_SEG_INODES_FULL或者FSP_SEG_INODES_FREE字段。
    Inode Entry 0 192 Inode记录
    Inode Entry 1    
    ……    
    Inode Entry 84    

    每个Inode Entry的结构如下表所示:

    Macro bits Desc
    FSEG_ID 8 该Inode归属的Segment ID,若值为0表示该slot未被使用
    FSEG_NOT_FULL_N_USED 8 FSEG_NOT_FULL链表上被使用的Page数量
    FSEG_FREE 16 完全没有被使用并分配给该Segment的Extent链表
    FSEG_NOT_FULL 16 至少有一个page分配给当前Segment的Extent链表,全部用完时,转移到FSEG_FULL上,全部释放时,则归还给当前表空间FSP_FREE链表
    FSEG_FULL 16 分配给当前segment且Page完全使用完的Extent链表
    FSEG_MAGIC_N 4 Magic Number
    FSEG_FRAG_ARR 0 4 属于该Segment的独立Page。总是先从全局分配独立的Page,当填满32个数组项时,就在每次分配时都分配一个完整的Extent,并在XDES PAGE中将其Segment ID设置为当前值
    …… ……  
    FSEG_FRAG_ARR 31 4 总共存储32个记录项

    看到这里,上面的图应该是理解了,当然书上还是给了一个简化的图:

    5.3 文件维护


         从上文我们可以看到,InnoDB通过Inode Entry来管理每个Segment占用的数据页,每个segment可以看做一个文件页维护单元。Inode Entry所在的inode page有可能存放满,因此又通过头Page维护了Inode Page链表。
          在ibd的第一个Page中还维护了表空间内Extent的FREE、FREE_FRAG、FULL_FRAG三个Extent链表;而每个Inode Entry也维护了对应的FREE、NOT_FULL、FULL三个Extent链表。这些链表之间存在着转换关系,以高效的利用数据文件空间。注意区别:表空间中的链表管理的是整个表空间中所有的簇,包括满簇、半满簇及空闲簇,而段的iNode信息中管理的是属于自己段中的满簇、半满簇及空闲簇。

    当创建一个新的索引时,实际上构建一个新的btree(btr_create),先为非叶子节点Segment分配一个inode entry,再创建root page,并将该segment的位置记录到root page中,然后再分配leaf segment的Inode entry,并记录到root page中。当删除某个索引后,该索引占用的空间需要能被重新利用起来。

    创建一个segment:

    函数入口:fseg_create_general,后面贴一下代码,主要是书上的解释。

    1.根据空间id得到表空间头信息。

    2. 从得到的表空间头信息分配Inode:具体实现为读取文件头Page并加锁(fsp_get_space_header),然后开始为其分配Inode Entry(fsp_alloc_seg_inode)。

      为了管理Inode Page,在文件头存储了两个Inode Page链表,一个链接已经用满的inode page,一个链接尚未用满的inode page。如果当前Inode Page的空间使用完了,就需要再分配一个inode page,并加入到FSP_SEG_INODES_FREE链表上(fsp_alloc_seg_inode_page)。对于独立表空间,通常一个inode page就足够了。

    下面看具体查找inode Page过程:首先判断FSP_SEG_INODES_FREE链表是否还有空闲页面,如果有,则从页面的数据存储位置开始扫描,没找一个Inode,先判断是否空闲(空闲表示其不归属任何segment,即FSEG_ID置为0)。找到则返回。找到这个且这个Inode为这个页最后一个Inode.则该inode page中的记录用满了,就从FSP_SEG_INODES_FREE链表上转移到FSP_SEG_INODES_FULL链表。如果FSP_SEG_INODES_FREE没有空闲的Inode页面,则重新分配一个inode页面,分配后把所有描述符里面的FSEG_ID置为0,重复上面过程。

    3.给新分配的Inode设置SEG_ID. 这个ID号要从表空间头信息的FSP_SEG_ID作为当前segment的seg id写入到inode entry中。同时更新FSP_SEG_ID的值为ID+1,作为下一个段的ID号。

    4.在完成inode entry的提取后,初始化这个Inode信息。把FSEG_NOT_FULL_N_USED置为0,初始化FSEG_FREE、FSEG_NOT_FULL,FSEG_FULL。

    5. 从这个段分配出一个页面。(这块逻辑不太懂)

    6.分配好页面后,通过缓存找到段的首页面(页面号为page+index)。就将该inode entry所在inode page的位置及页内偏移量存储到段首页,10个字节的inode信息包括:

    Macro bytes Desc
    FSEG_HDR_SPACE 4 描述该segment的inode page所在的space id (目前的实现来看,感觉有点多余…)
    FSEG_HDR_PAGE_NO 4 描述该segment的inode page的page no
    FSEG_HDR_OFFSET 2 inode page内的页内偏移量

    至此段就分配完成了,以后如果需要在这个段中分配空间,只需要找到其首页,然后根据对应的Inode分配空间。

    Creates a new segment.
    @return the block where the segment header is placed, x-latched, NULL
    if could not create segment because of lack of space */
    UNIV_INTERN
    buf_block_t*
    fseg_create_general(
    /*================*/
        ulint    space,    /*!< in: space id */
        ulint    page,    /*!< in: page where the segment header is placed: if
                this is != 0, the page must belong to another segment,
                if this is 0, a new page will be allocated and it
                will belong to the created segment */
        ulint    byte_offset, /*!< in: byte offset of the created segment header
                on the page */
        ibool    has_done_reservation, /*!< in: TRUE if the caller has already
                done the reservation for the pages with
                fsp_reserve_free_extents (at least 2 extents: one for
                the inode and the other for the segment) then there is
                no need to do the check for this individual
                operation */
        mtr_t*    mtr)    /*!< in: mtr */
    {
        ulint        flags;
        ulint        zip_size;
        fsp_header_t*    space_header;
        fseg_inode_t*    inode; //typedef byte fseg_inode_t;
        ib_id_t        seg_id;
        buf_block_t*    block    = 0; /* remove warning */
        fseg_header_t*    header    = 0; /* remove warning */
        rw_lock_t*    latch;
        ibool        success;
        ulint        n_reserved;
        ulint        i;
    
        ut_ad(mtr);
        ut_ad(byte_offset + FSEG_HEADER_SIZE
              <= UNIV_PAGE_SIZE - FIL_PAGE_DATA_END);
    
        latch = fil_space_get_latch(space, &flags);
        zip_size = dict_table_flags_to_zip_size(flags);
    
        if (page != 0) {
            block = buf_page_get(space, zip_size, page, RW_X_LATCH, mtr);
            header = byte_offset + buf_block_get_frame(block);
        }
    
        ut_ad(!mutex_own(&kernel_mutex)
              || mtr_memo_contains(mtr, latch, MTR_MEMO_X_LOCK));
    
        mtr_x_lock(latch, mtr);
    
        if (rw_lock_get_x_lock_count(latch) == 1) {
            /* This thread did not own the latch before this call: free
            excess pages from the insert buffer free list */
    
            if (space == IBUF_SPACE_ID) {
                ibuf_free_excess_pages();
            }
        }
    
        if (!has_done_reservation) {
            success = fsp_reserve_free_extents(&n_reserved, space, 2,
                               FSP_NORMAL, mtr);
            if (!success) {
                return(NULL);
            }
        }
    
        space_header = fsp_get_space_header(space, zip_size, mtr);//详见
    
        inode = fsp_alloc_seg_inode(space_header, mtr);//申请inode entry 详见     if (inode == NULL) {
    
            goto funct_exit;
        }
    
        /* Read the next segment id from space header and increment the
        value in space header */
    
        seg_id = mach_read_from_8(space_header + FSP_SEG_ID);//设置下一下seg id
    
        mlog_write_ull(space_header + FSP_SEG_ID, seg_id + 1, mtr);
       
        /**
     *#define FSEG_ID 0
     *#define FSEG_NOT_FULL_N_USED 8
     *#define FSEG_FREE 12
     
     *#define FSEG_NOT_FULL (12 + FLST_BASE_NODE_SIZE)
     *#define FLST_BASE_NODE_SIZE (4 + 2 * FIL_ADDR_SIZE)
     *#define FIL_ADDR_SIZE 6
     *
     *#define FSEG_FULL (12 + 2 * FLST_BASE_NODE_SIZE) 
     *
     */
        mlog_write_ull(inode + FSEG_ID, seg_id, mtr); 
        mlog_write_ulint(inode + FSEG_NOT_FULL_N_USED, 0, MLOG_4BYTES, mtr);
    
        flst_init(inode + FSEG_FREE, mtr); //初始化inode中的seg list 详见
        flst_init(inode + FSEG_NOT_FULL, mtr);
        flst_init(inode + FSEG_FULL, mtr);
    
        mlog_write_ulint(inode + FSEG_MAGIC_N, FSEG_MAGIC_N_VALUE,
                 MLOG_4BYTES, mtr);
       
        //#define FSEG_FRAG_ARR_N_SLOTS (FSP_EXTENT_SIZE / 2) 64/2=32 for (i = 0; i < FSEG_FRAG_ARR_N_SLOTS; i++) {
            fseg_set_nth_frag_page_no(inode, i, FIL_NULL, mtr); //设置frag 碎片 详见
        }
    
        if (page == 0) {
            block = fseg_alloc_free_page_low(space, zip_size,
                             inode, 0, FSP_UP, mtr, mtr);
    
            if (block == NULL) {
    
                fsp_free_seg_inode(space, zip_size, inode, mtr);
    
                goto funct_exit;
            }
    
            ut_ad(rw_lock_get_x_lock_count(&block->lock) == 1);
    
            header = byte_offset + buf_block_get_frame(block);
            mlog_write_ulint(buf_block_get_frame(block) + FIL_PAGE_TYPE,
                     FIL_PAGE_TYPE_SYS, MLOG_2BYTES, mtr);
        }
        
        //设置fset_header信息
        mlog_write_ulint(header + FSEG_HDR_OFFSET,page_offset(inode), MLOG_2BYTES, mtr);
    
        mlog_write_ulint(header + FSEG_HDR_PAGE_NO,page_get_page_no(page_align(inode)),MLOG_4BYTES, mtr);
    
        mlog_write_ulint(header + FSEG_HDR_SPACE, space, MLOG_4BYTES, mtr);
    
    funct_exit:
        if (!has_done_reservation) {
    
            fil_space_release_free_extents(space, n_reserved);
        }
    
        return(block);
    }

    分配数据页函数 fsp_alloc_free_page
    表空间Extent的分配函数fsp_alloc_free_extent ,不在此展开。

    对应的还有释放Segment 当我们删除索引或者表时,需要删除btree(btr_free_if_exists),先删除除了root节点外的其他部分(btr_free_but_not_root),再删除root节点(btr_free_root)
    由于数据操作都需要记录redo,为了避免产生非常大的redo log,leaf segment通过反复调用函数fseg_free_step来释放其占用的数据页。

    六 创建B+索引

         上面我们已经大概了解了innodb的文件管理方式,核心目的是为了管理好B+索引。
          ibd文件中真正构建起用户数据的结构是BTREE,在你创建一个表时,已经基于显式或隐式定义的主键构建了一个btree,其叶子节点上记录了行的全部列数据(加上事务id列及回滚段指针列);如果你在表上创建了二级索引,其叶子节点存储了键值加上聚集索引键值。所以书上贴一段创建B+索引的代码。网上找了5.6.15版本的。这个函数就是创建一个B+树,只是概念上的,还没有真正的数据写入。

        相关知识点:B+树,索引,段,区/簇(extent),页 已经串起来了。下一篇可以继续整理索引了。

    Creates the root node for a new index tree.
    @return	page number of the created root, FIL_NULL if did not succeed */
    UNIV_INTERN
    ulint
    btr_create(
    /*=======*/
    	ulint		type,	/*!< in: type of the index */
    	ulint		space,	/*!< in: space where created */
    	ulint		zip_size,/*!< in: compressed page size in bytes
    				or 0 for uncompressed pages */
    	index_id_t	index_id,/*!< in: index id */
    	dict_index_t*	index,	/*!< in: index */
    	mtr_t*		mtr)	/*!< in: mini-transaction handle */
    {
    	ulint		page_no;
    	buf_block_t*	block;
    	buf_frame_t*	frame;
    	page_t*		page;
    	page_zip_des_t*	page_zip;
    
    	/* Create the two new segments (one, in the case of an ibuf tree) for
    	the index tree; the segment headers are put on the allocated root page
    	(for an ibuf tree, not in the root, but on a separate ibuf header
    	page) */
    
    	if (type & DICT_IBUF) {
    		/* Allocate first the ibuf header page */
    		buf_block_t*	ibuf_hdr_block = fseg_create(
    			space, 0,
    			IBUF_HEADER + IBUF_TREE_SEG_HEADER, mtr);
    
    		buf_block_dbg_add_level(
    			ibuf_hdr_block, SYNC_IBUF_TREE_NODE_NEW);
    
    		ut_ad(buf_block_get_page_no(ibuf_hdr_block)
    		      == IBUF_HEADER_PAGE_NO);
    		/* Allocate then the next page to the segment: it will be the
    		tree root page */
    
    		block = fseg_alloc_free_page(
    			buf_block_get_frame(ibuf_hdr_block)
    			+ IBUF_HEADER + IBUF_TREE_SEG_HEADER,
    			IBUF_TREE_ROOT_PAGE_NO,
    			FSP_UP, mtr);
    		ut_ad(buf_block_get_page_no(block) == IBUF_TREE_ROOT_PAGE_NO);
    	} else {
    #ifdef UNIV_BLOB_DEBUG
    		if ((type & DICT_CLUSTERED) && !index->blobs) {
    			mutex_create(PFS_NOT_INSTRUMENTED,
    				     &index->blobs_mutex, SYNC_ANY_LATCH);
    			index->blobs = rbt_create(sizeof(btr_blob_dbg_t),
    						  btr_blob_dbg_cmp);
    		}
    #endif /* UNIV_BLOB_DEBUG */
    		block = fseg_create(space, 0,
    				    PAGE_HEADER + PAGE_BTR_SEG_TOP, mtr);
    	}
    
    	if (block == NULL) {
    
    		return(FIL_NULL);
    	}
    
    	page_no = buf_block_get_page_no(block);
    	frame = buf_block_get_frame(block);
    
    	if (type & DICT_IBUF) {
    		/* It is an insert buffer tree: initialize the free list */
    		buf_block_dbg_add_level(block, SYNC_IBUF_TREE_NODE_NEW);
    
    		ut_ad(page_no == IBUF_TREE_ROOT_PAGE_NO);
    
    		flst_init(frame + PAGE_HEADER + PAGE_BTR_IBUF_FREE_LIST, mtr);
    	} else {
    		/* It is a non-ibuf tree: create a file segment for leaf
    		pages */
    		buf_block_dbg_add_level(block, SYNC_TREE_NODE_NEW);
    
    		if (!fseg_create(space, page_no,
    				 PAGE_HEADER + PAGE_BTR_SEG_LEAF, mtr)) {
    			/* Not enough space for new segment, free root
    			segment before return. */
    			btr_free_root(space, zip_size, page_no, mtr);
    
    			return(FIL_NULL);
    		}
    
    		/* The fseg create acquires a second latch on the page,
    		therefore we must declare it: */
    		buf_block_dbg_add_level(block, SYNC_TREE_NODE_NEW);
    	}
    
    	/* Create a new index page on the allocated segment page */
    	page_zip = buf_block_get_page_zip(block);
    
    	if (page_zip) {
    		page = page_create_zip(block, index, 0, 0, mtr);
    	} else {
    		page = page_create(block, mtr,
    				   dict_table_is_comp(index->table));
    		/* Set the level of the new index page */
    		btr_page_set_level(page, NULL, 0, mtr);
    	}
    
    	block->check_index_page_at_flush = TRUE;
    
    	/* Set the index id of the page */
    	btr_page_set_index_id(page, page_zip, index_id, mtr);
    
    	/* Set the next node and previous node fields */
    	btr_page_set_next(page, page_zip, FIL_NULL, mtr);
    	btr_page_set_prev(page, page_zip, FIL_NULL, mtr);
    
    	/* We reset the free bits for the page to allow creation of several
    	trees in the same mtr, otherwise the latch on a bitmap page would
    	prevent it because of the latching order */
    
    	if (!(type & DICT_CLUSTERED)) {
    		ibuf_reset_free_bits(block);
    	}
    
    	/* In the following assertion we test that two records of maximum
    	allowed size fit on the root page: this fact is needed to ensure
    	correctness of split algorithms */
    
    	ut_ad(page_get_max_insert_size(page, 2) > 2 * BTR_PAGE_MAX_REC_SIZE);
    
    	return(page_no);
    }
    

    ************************************************

    真是博大精深,看了书不太懂,C++源码的也是头大。当然对于开发来说,多了解知识更有助于高效率使用。

     

    参考:

    http://mysql.taobao.org/monthly/2016/02/01/

    《MYSQL运维内参》

    https://dev.mysql.com/doc/refman/5.7/en/innodb-file-space.html

    展开全文
  • MySQL数据结构

    千次阅读 2020-09-06 20:40:23
    最近在学习Mysql数据结构,这里整理下。因为主流存储引擎是InnoDB,学习的也是它。这里介绍的也是InnoDB。 数据页 在操作系统中,我们知道为了跟磁盘交互,内存也是分页的,一页大小4KB。同样的在MySQL中为了...

    最近在学习Mysql的数据结构,这里整理下。因为主流存储引擎是InnoDB,学习的也是它。这里介绍的也是InnoDB。

    数据页

    在操作系统中,我们知道为了跟磁盘交互,内存也是分页的,一页大小4KB。同样的在MySQL中为了提高吞吐率,数据也是分页的,不过MySQL的数据页大小是16KB。(确切的说是InnoDB数据页大小16KB)。详细学习可以参考官网

    为了详细说明,这里先用图介绍一下页的结构:

    而在MySQL内存中,多个这样的数据结构作为节点构成一个双向链表。

     

    File Header

    从上边的图也可以发现,它描述的是页外部的一些信息,比如上一页下一页等。看下它的字段结构:

    共计 38 字节,重要的有

    • FIL_PAGE_SPACE_OR_CHKSUM

    即校验和,需要过计算机的都知道,为了快速比较、保证数据的完整性防止遭到破坏等,经常采用给一串数据加上校验和来做自校验。这在网络传输中很常用。

    • FIL_PAGE_OFFSET

    即页号,InnoDB通过页号来可以唯一定位一个页

    • FIL_PAGE_TYPE

    即页的类型,InnoDB为了不同的目的而把页分为不同的类型。存储数据的为数据页,更多类型可以参考 PAGE_TYPE 介绍

    • FIL_PAGE_PREV、FIL_PAGE_NEXT

    分别指向上一页和下一页

     

     

    Page Header

    既然是header,肯定就是存储页内的一些状态、汇总信息,如本页有多少条记录等。总计 56 个字节。各字段长度如下:

    说明如下:

    • PAGE_N_DIR_SLOTS

    页内槽的个数

    • PAGE_HEAP_TOP

    第一条记录地址

    • PAGE_N_HEAP

    页内记录数,含最大最小记录及标记删除的记录

     

     

     

    Infimum + Supremum

     

    User Records

     

    Free Space

     

    Page Directory

     

    File Tailer

     

    待续

     

    展开全文
  • mysql存储树状结构数据

    千次阅读 2018-03-29 22:13:29
    分析树形数据JSON格式的树形结构数据需要保存mysql中。树形图如下: 分析成文本如图: 存到表中的结构为: 需求一般树形结构数据使用需求有两点:显示整棵树的数据select * from treeNodes1给出某个点,显示到达...

    分析树形数据

    JSON格式的树形结构数据需要保存到mysql中。

    树形图如下: 
     
    分析成文本如图: 

    存到表中的结构为: 

    需求

    一般树形结构的数据使用需求有两点:

    显示整棵树的数据

    select * from treeNodes
    • 1

    给出某个点,显示到达该点所经过的路径

    a=select * from treeNodes where id='7'
    b=select * from treeNodes where id=a.pid
    c=select * from treeNodes where id=b.pid
    • 1
    • 2
    • 3

    …依次递归到Root节点。

    还可以使用如下几种方法获取经过的路径:

    方法一利用函数来得到所有子节点号

    创建一个function getChildLst, 得到一个由所有子节点号组成的字符串. 

    mysql> delimiter / 
    mysql> 
    mysql> CREATE FUNCTION getChildLst(rootId INT) 
    -> RETURNS varchar(1000) 
    -> BEGIN 
    -> DECLARE sTemp VARCHAR(1000); 
    -> DECLARE sTempChd VARCHAR(1000); 
    -> 
    -> SET sTemp = ‘$’; 
    -> SET sTempChd =cast(rootId as CHAR); 
    -> 
    -> WHILE sTempChd is not null DO 
    -> SET sTemp = concat(sTemp,’,’,sTempChd); 
    -> SELECT group_concat(id) INTO sTempChd FROM treeNodes where FIND_IN_SET(pid,sTempChd)>0; 
    -> END WHILE; 
    -> RETURN sTemp; 
    -> END 
    -> // 
    Query OK, 0 rows affected (0.00 sec)

    mysql> 
    mysql> delimiter ; 

    使用我们直接利用find_in_set函数配合这个getChildlst来查找 

    mysql> select getChildLst(1); 
    +—————–+ 
    | getChildLst(1) | 
    +—————–+ 
    | $,1,2,3,4,5,6,7 | 
    +—————–+ 
    1 row in set (0.00 sec)

    mysql> select * from treeNodes 
    -> where FIND_IN_SET(id, getChildLst(1)); 
    +—-+———-+——+ 
    | id | nodename | pid | 
    +—-+———-+——+ 
    | 1 | A | 0 | 
    | 2 | B | 1 | 
    | 3 | C | 1 | 
    | 4 | D | 2 | 
    | 5 | E | 2 | 
    | 6 | F | 3 | 
    | 7 | G | 6 | 
    +—-+———-+——+ 
    7 rows in set (0.01 sec)

    mysql> select * from treeNodes 
    -> where FIND_IN_SET(id, getChildLst(3)); 
    +—-+———-+——+ 
    | id | nodename | pid | 
    +—-+———-+——+ 
    | 3 | C | 1 | 
    | 6 | F | 3 | 
    | 7 | G | 6 | 
    +—-+———-+——+ 
    3 rows in set (0.01 sec) 

    优点: 简单,方便,没有递归调用层次深度的限制 (max_sp_recursion_depth,最大255) ;

    缺点:长度受限,虽然可以扩大 RETURNS varchar(1000),但总是有最大限制的。

    MySQL目前版本( 5.1.33-community)中还不支持function 的递归调用。

    方法二利用临时表和过程递归

    创建存储过程如下。 
    createChildLst 为递归过程,showChildLst为调用入口过程,准备临时表及初始化。 

    mysql> delimiter // 
    mysql> 
    mysql> # 入口过程 
    mysql> CREATE PROCEDURE showChildLst (IN rootId INT) 
    -> BEGIN 
    ->CREATE TEMPORARY TABLE IF NOT EXISTS tmpLst 
    -> (sno int primary key auto_increment,id int,depth int); 
    ->DELETE FROM tmpLst; 
    -> 
    ->CALL createChildLst(rootId,0); 
    -> 
    ->select tmpLst.,treeNodes. from tmpLst,treeNodes where tmpLst.id=treeNodes.id order by tmpLst.sno; 
    -> END; 
    -> // 
    Query OK, 0 rows affected (0.00 sec) 
    mysql> 
    mysql> # 递归过程 
    mysql> CREATE PROCEDURE createChildLst (IN rootId INT,IN nDepth INT) 
    -> BEGIN 
    ->DECLARE done INT DEFAULT 0; 
    ->DECLARE b INT; 
    ->DECLARE cur1 CURSOR FOR SELECT id FROM treeNodes where pid=rootId; 
    ->DECLARE CONTINUE HANDLER FOR NOT FOUND SET done = 1; 
    -> 
    ->insert into tmpLst values (null,rootId,nDepth); 
    -> 
    ->OPEN cur1; 
    -> 
    ->FETCH cur1 INTO b; 
    ->WHILE done=0 DO 
    ->CALL createChildLst(b,nDepth+1); 
    ->FETCH cur1 INTO b; 
    ->END WHILE; 
    -> 
    ->CLOSE cur1; 
    -> END; 
    -> // 
    Query OK, 0 rows affected (0.00 sec) 
    mysql> delimiter ; 

    调用时传入结点 

    mysql> call showChildLst(1); 
    +-----+------+-------+----+----------+------+ 
    | sno | id | depth | id | nodename | pid| 
    +-----+------+-------+----+----------+------+ 
    | 4 |1 | 0 |1 | A|0 | 
    | 5 |2 | 1 |2 | B|1 | 
    | 6 |4 | 2 |4 | D|2 | 
    | 7 |5 | 2 |5 | E|2 | 
    | 8 |3 | 1 |3 | C|1 | 
    | 9 |6 | 2 |6 | F|3 | 
    |10 |7 | 3 |7 | G|6 | 
    +-----+------+-------+----+----------+------+ 
    7 rows in set (0.13 sec) 
    Query OK, 0 rows affected, 1 warning (0.14 sec) 
    mysql> 
    mysql> call showChildLst(3); 
    +-----+------+-------+----+----------+------+ 
    | sno | id | depth | id | nodename | pid| 
    +-----+------+-------+----+----------+------+ 
    | 1 |3 | 0 |3 | C|1 | 
    | 2 |6 | 1 |6 | F|3 | 
    | 3 |7 | 2 |7 | G|6 | 
    +-----+------+-------+----+----------+------+ 
    3 rows in set (0.11 sec) 
    Query OK, 0 rows affected, 1 warning (0.11 sec) 

    depth 为深度,这样可以在程序进行一些显示上的格式化处理。类似于oracle中的 level 伪列。sno 仅供排序控制。这样你还可以通过临时表tmpLst与数据库中其它表进行联接查询。

    MySQL中你可以利用系统参数 max_sp_recursion_depth 来控制递归调用的层数上限。如下例设为12. 

    mysql> set max_sp_recursion_depth=12; 
    Query OK, 0 rows affected (0.00 sec) 

    优点 : 可以更灵活处理,及层数的显示。并且可以按照树的遍历顺序得到结果。 
    缺点 : 递归有255的限制。

    方法三利用中间表和过程

    (本方法由yongyupost2000提供样子改编) 
    创建存储过程如下。由于MySQL中不允许在同一语句中对临时表多次引用,只以使用普通表tmpLst来实现了。当然你的程序中负责在用完后清除这个表。 

    delimiter // 
    drop PROCEDURE IF EXISTSshowTreeNodes_yongyupost2000// 
    CREATE PROCEDURE showTreeNodes_yongyupost2000 (IN rootid INT) 
    BEGIN 
    DECLARE Level int ; 
    drop TABLE IF EXISTS tmpLst; 
    CREATE TABLE tmpLst ( 
    id int, 
    nLevel int, 
    sCort varchar(8000) 
    ); 
    Set Level=0 ; 
    INSERT into tmpLst SELECT id,Level,ID FROM treeNodes WHERE PID=rootid; 
    WHILE ROW_COUNT()>0 DO 
    SET Level=Level+1 ; 
    INSERT into tmpLst 
    SELECT A.ID,Level,concat(B.sCort,A.ID) FROM treeNodes A,tmpLst B 
    WHEREA.PID=B.ID AND B.nLevel=Level-1; 
    END WHILE; 
    END; 
    delimiter ; 
    CALL showTreeNodes_yongyupost2000(0); 

    执行完后会产生一个tmpLst表,nLevel 为节点深度,sCort 为排序字段。 
    使用方法 

    SELECT concat(SPACE(B.nLevel*2),'+--',A.nodename) 
    FROM treeNodes A,tmpLst B 
    WHERE A.ID=B.ID 
    ORDER BY B.sCort; 

    优点 : 层数的显示。并且可以按照树的遍历顺序得到结果。没有递归限制。 
    缺点 : MySQL中对临时表的限制,只能使用普通表,需做事后清理。

    存储结构对比优化

    假设有如下一棵树: 

    方法一存储父节点

    要存储于数据库中,最简单直接的方法,就是存储每个元素的父节点ID。 
    暂且把这种方法命名依赖父节点法,因此表结构设计如下: 
     
    存储的数据如下格式: 
     
    这种结构下,如果查询某一个节点的直接子节点,十分容易,比如要查询D节点的子节点。

    select * from tree1 where parentid=4
    • 1

    如果要插入某个节点,比如在D节点下,再次插入一个M节点。 
    只需要如下SQL:

    INSERT INTO tree1 (value,parentid) VALUES('M',4);
    • 1

    这种结构在查找某个节点的所有子节点,就稍显复杂,无论是SELECT还是DELETE都可能涉及到获取所有子节点的问题。比如要删除一个节点并且该节点的子节点也要全部删除,那么首先要获得所有子节点的ID,因为子节点并不只是直接子节点,还可能包含子节点的子节点。比如删除D节点及其子节点,必须先查出D节点下的所有子节点,然后再做删除,SQL如下: 

    select nodeid from tree1 where parentid=4 --返回8,9 
    select nodeid from tree1 where parentid in (8,9) --返回10,11,12 
    select nodeid from tree1 where parentid in (10,11,12) --返回空 
    delete from tree1 where nodeid in (4,8,9,10,11,12) 

    如果是只删除D节点,对于其它节点不做删除而是做提升,那么必须先修改子节点的parentid,然后才能删除D节点。 
    正如上面演示的,对于这种依赖父节点法,最大的缺点就是无法直接获得某个节点的所有子节点。因此如果要select所有的子节点,需要繁琐的步骤,这不利于做聚合操作。 
    对于某些数据库产品,支持递归查询语句的,比如微软的SQL Server,可以使用CTE技术实现递归查询。比如,要查询D节点的所有子节点。只需要如下语句: 

    WITH tmp AS( 
    SELECT * FROM Tree1 WHERE nodeid = 4 
    UNION ALL 
    SELECT a.* FROM Tree1 AS a,tmp AS b WHERE a.parentid = b. nodeid 

    SELECT * FROM tmp 

    但是对于那些不支持递归查询的数据库来说,实现起来就比较复杂了。

    方法二存储路径

    还有一种比较土的方法,就是存储路径。暂且命名为路径枚举法。 
    这种方法,将存储根结点到每个节点的路径。 
     
    这种数据结构,可以一眼就看出子节点的深度。 
    如果要查询某个节点下的子节点,只需要根据path的路径去匹配,比如要查询D节点下的所有子节点。

    select * from tree2 where path like '%/4/%'
    • 1

    或者出于效率考虑,直接写成

    select * from tree2 where path like '1/4/%'
    • 1

     
    如果要做聚合操作,也很容易,比如查询D节点下一共有多少个节点。

    select count(*) from tree2 where path like '1/4/%';
    • 1

    要插入一个节点,则稍微麻烦点。要插入自己,然后查出父节点的Path,并且把自己生成的ID更新到path中去。比如,要在L节点后面插入M节点。 
    首先插入自己M,然后得到一个nodeid比如nodeid=13,然后M要插入到L后面,因此,查出L的path为1/4/8/12/,因此update M的path为1/4/8/12/13 

    update tree2 set 
    path=(select path from tree2 where nodeid=12) --此处开始拼接 
    ||last_insert_rowid()||'/' 
    where 
    nodeid= last_insert_rowid(); 

    这种方法有一个明显的缺点就是path字段的长度是有限的,这意味着,不能无限制的增加节点深度。因此这种方法适用于存储小型的树结构。

    方法三存储关系表和深度

    下面介绍一种方法,称之为闭包表。 
    该方法记录了树中所有节点的关系,不仅仅只是直接父子关系,它需要使用2张表,除了节点表本身之外,还需要使用1张表来存储节祖先点和后代节点之间的关系(同时增加一行节点指向自身),并且根据需要,可以增加一个字段,表示深度。因此这种方法数据量很多。设计的表结构如下: 
    Tree3表: 
     
    NodeRelation表: 
     
    如例子中的树,插入的数据如下: 
    Tree3表的数据 
     
    NodeRelation表的数据 
     
    可以看到,NodeRelation表的数据量很多。但是查询非常方便。比如,要查询D节点的子元素 
    只需要

    select * from NodeRelation where ancestor=4;
    • 1

    要查询节点D的直接子节点,则加上depth=1

    select * from NodeRelation where ancestor=4 and depth=1;
    • 1

    要查询节点J的所有父节点,SQL:

    select * from NodeRelation where descendant=10;
    • 1

    如果是插入一个新的节点,比如在L节点后添加子节点M,则插入的节点除了M自身外,还有对应的节点关系。即还有哪些节点和新插入的M节点有后代关系。这个其实很简单,只要和L节点有后代关系的,和M节点必定会有后代关系,并且和L节点深度为X的和M节点的深度必定为X+1。因此,在插入M节点后,找出L节点为后代的那些节点作为和M节点之间有后代关系,插入到数据表。 

    INSERT INTO tree3 (value) VALUES('M');--插入节点 
    INSERT INTO NodeRelation(ancestor,descendant,depth) 
    select n.ancestor,last_insert_rowid(),n.depth+1--此处深度+1作为和M节点的深度 
    from NodeRelation n 
    where n.descendant=12 
    Union ALL 
    select last_insert_rowid() ,last_insert_rowid(),0 --加上自身 

    在某些并不需要使用深度的情况下,甚至可以不需要depth字段。 
    如果要删除某个节点也很容易,比如,要删除节点D,这种情况下,除了删除tree3表中的D节点外,还需要删除NodeRelation表中的关系。 
    首先以D节点为后代的关系要删除,同时以D节点的后代为后代的这些关系也要删除: 

    delete from NodeRelation where descendant in 
    (select descendant from NodeRelation where ancestor=4 ); 

    –查询以D节点为祖先的那些节点,即D节点的后代。 
    这种删除方法,虽然彻底,但是它也删除了D节点和它原本的子节点的关系。 
    如果只是想割裂D节点和A节点的关系,而对于它原有的子节点的关系予以保留,则需要加入限定条件。 
    限制要删除的关系的祖先不以D为祖先,即如果这个关系以D为祖先的,则不用删除。因此把上面的SQL加上条件。 

    delete from NodeRelation where descendant in 
    (select descendant from NodeRelation where ancestor=4 ); 

    –查询以D节点为祖先的那些节点,即D节点的后代。 

    and ancestor not in (select descendant from NodeRelation where ancestor =4 ) 

    上面的SQL用文字描述就是,查询出D节点的后代,如果一个关系的祖先不属于D节点的后代,并且这个关系的后代属于D节点的后代,就删除它。 
    这样的删除,保留了D节点自身子节点的关系,如上面的例子,实际上删除的节点关系为: 
     
    如果要删除节点H,则为 
     
    总结: 
    上面主要讲了3种方式,各有优点缺点。可以根据实际需要,选择合适的数据模型。

    参考链接: 
    http://blog.csdn.net/sky786905664/article/details/52742392 
    http://langgufu.iteye.com/blog/1891798

    展开全文
  • mysqlmysql索引存储结构和特点

    万次阅读 2019-08-22 09:14:40
    MySQL索引存储结构和特点 一 理解索引的特性 二 索引的各种存储结构及其优缺点 (一)二叉树 ​(二)红黑树 ...索引是帮助MySQL高效获取数据的排好序的数据结构 索引存储在文件里 二 索引的各种存...
  • Mysql数据结构

    千次阅读 2019-12-09 17:41:32
    文章目录数据页数据库中的存储结构数据页的结构数据结构的角度看B+树结构-决定特性磁盘IO数据库缓冲池缓冲池的一些命令查看数据页加载的三种方式结构-决定特性 数据页 数据库中的存储结构 记录是按照行来存储的...
  • MySQL InnoDB 存储结构

    千次阅读 2018-09-24 00:50:38
    MySQL InnoDB 存储结构 InnoDB存储引擎的关键特性包括: 插入缓冲(Insert Buffer) 两次写(Double Write) 自适应哈希索引(Adaptive Hash Index) 异步IO(Async IO) 刷新邻接页 从逻辑上讲 所有的数据都被...
  • 参考:官方内部文档手册:... 腾讯游戏DBA团队的Innodb页面存储结构:Innodb页面存储结构-1 Innodb页面存储结构-2 淘宝内核月报MySQL · 引擎特性 · InnoDB 数据页解析:...
  • mysql底层数据结构与算法

    千次阅读 2021-03-16 17:29:26
    目录 mysql为什么要合理使用数据结构? 索引数据结构选型: 二叉树 ... 数据存储mysql数据库磁盘位置是无序的,是不均匀分布的,为了解决持续的io流消耗问题,就必须使用合理的数据结构 ...
  • mysql数据结构

    千次阅读 2018-12-31 22:52:17
    在刚才新建表的过程中,我们提到了数据类型,MySQL数据类型和其他编程语言大同小异,下表是一些 MySQL 常用数据类型: 整数型:整数除了 INT 外,还有 TINYINT、SMALLINT、MEDIUMINT、BIGINT。 字符型:CHAR 和 ...
  • Mysql索引数据结构

    万次阅读 多人点赞 2018-08-26 11:55:58
    首先,数据库索引使用树来存储,因为树的查询效率高,而且二叉查找树还可以保持数据的有序。 那么索引为什么没有使用二叉树来实现呢? 其实从算法逻辑上讲,二叉查找树的查找速度和比较次数都是最小的,但是从...
  • mysql存储树形结构数据

    万次阅读 2017-12-03 23:46:58
    JSON格式的树形结构数据需要保存mysql中。 树形图如下: 分析成文本如图: 存到表中的结构为: 需求 一般树形结构数据使用需求有两点: 显示整棵树的数据 select * from treeNodes 给出某个点,显示...
  • 近期看了一篇文章是关于数据库的工作原理的,其中提到了两种数据库的数据结构一种是阵列,一种是哈希表,我想请问各位大牛mysql db在磁盘上存储是如何存储的呢?是阵列还是哈希表存储呢??
  • MySQL存储结构的使用

    千次阅读 2015-08-20 13:23:08
    今天公司老大让我做一个MySQL的调研工作,是关于MySQL存储结构的使用。这里我会通过3个例子来介绍一下MySQL存储结构的使用过程,以及一些需要注意的点。
  • 数据结构:八大数据结构分类

    万次阅读 多人点赞 2018-09-05 18:23:28
    每一种数据结构都有着独特的数据存储方式,下面为大家介绍它们的结构和优缺点。 1、数组 数组是可以再内存中连续存储多个元素的结构,在内存中的分配也是连续的,数组中的元素通过数组下标进行访问,数组下标从0...
  • mysql存储引擎

    万次阅读 多人点赞 2019-07-31 19:28:44
    数据库存储引擎 数据库存储引擎是数据库底层软件组织,数据库管理系统(DBMS)使用数据引擎进行...因为在关系数据库中数据存储是以表的形式存储的,所以存储引擎也可以称为表类型(Table Type,即存储和操作此表...
  • mysql中,索引就是帮助mysql快速找到某条数据的一种数据结构,它是排好序的,独立于mysql数据之外的。 索引数据结构分为哪几种 二叉树、红黑树、Hash表、B树。 在这里我们主要介绍hash表和B树 Hash表 什么是hash...
  • Mysql的Mysam存储引擎和Innodb存储引擎的索引的数据结构都是B+树结构。 一、什么是B+树结构? B+树结构是一种多路查找树的结构,该数据结构有以下特点: 根节点至少有两个子结点。 非根节点至少有m/2个关键字和...
  • MySQL - 剖析MySQL索引底层数据结构

    千次阅读 2020-07-18 16:51:14
    文章目录Pre Pre 什么是索引? 通俗的说就是为了提高效率专门设计的一种 排好序的数据结构。 怎么理解呢? 举个例子哈 如上数据 ,假设有个SQL select * from t where col2 = 22 ;
  • mysql 索引数据结构(笔记)

    千次阅读 2020-03-12 12:32:09
    索引的用途:帮助mysql高效获取数据数据结构。 索引使用策略及优化: mysql优化主要分为结构优化和查询优化。 一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化,增加了顺序访问...
  • MySQL索引的本质,MySQL索引的实现,MySQL索引的数据结构
  • Mysql数据结构及算法原理

    万次阅读 2018-04-06 21:01:42
    特别需要说明的是,MySQL支持诸多存储引擎,而各种存储引擎对索引的支持也各不相同,因此MySQL数据库支持多种索引类型,如BTree索引,哈希索引,全文索引等等。为了避免混乱,本文将只关注于BTree索引,因为这是平常...
  • MySQL数据结构以及辅助索引的使用

    千次阅读 2019-09-28 19:20:22
    MySQL数据结构以及辅助索引的使用。 InnoDB到底隐藏了什么小秘密?
  • 深入理解MySQL索引底层数据结构与算法

    万次阅读 多人点赞 2018-10-10 11:10:58
    目录 一 理解索引的特性 二 索引的各种存储结构及其优缺点 ...索引是帮助MySQL高效获取数据的排好序的数据结构 索引存储在文件里 二 索引的各种存储结构及其优缺点 在开始讲这一小节之前,我们先来看一...
  • Spark使用Java读取mysql数据保存数据到mysql

    千次阅读 热门讨论 2017-11-07 20:17:39
    基于java应用需要利用Spark读取mysql数据进行数据分析,然后将分析结果保存到mysql中。
  • MySQL 复制表结构数据

    千次阅读 2018-05-14 21:27:05
    like方法复制生成一个新表,包括其备注、索引、主键外键、存储引擎等 CREATE TABLE IF NOT EXISTS like_table2 (LIKE table2); 二、SELECT方法 select方法只复制字段属性,原表的主键、索引、表备注、存储引擎...
  • mysql知识点整理】 --- mysql索引底层数据结构

    千次阅读 多人点赞 2020-02-28 12:34:47
    文章目录1 什么是索引 1 什么是索引 索引是帮助MySQL高效的获取数据数据结构
  • MySQL索引存储结构(5种)

    千次阅读 2019-10-10 13:22:28
    索引是帮助MySQL高效获取数据的排好序的数据结构MySQL数据库索引存储结构一般有以下几种。 二叉树 红黑树 HASH B-Tree B+Tree(现在常用) 首先我们要了解的是:索引文件是存储在磁盘中的,cpu到磁盘拿取数据...
  • MySQL:简述MySQL数据库的结构图与存储引擎 一、MySQL数据库的结构图 二、MySQL数据库的存储引擎 &amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;MySQL数据库的存储引擎...
  • 线上已经有正在跑的项目了但是产品需求有调整重新开发的新项目: 1:数据库新增各种字段, 2:数据存储类型不同 之前没有处理过这方面的经验!大伙有没有什么可以指教的?

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 357,402
精华内容 142,960
关键字:

mysql数据存储结构

mysql 订阅