Indexes

Overall Organization Of Data In Disks Assuming we have a 256KB disk. Disk Blocks: The basic units of storage on the disk, each 4 KB in size. The disk is divided into these blocks, numbered from 0 to N-1 (where N is the total number of blocks). Inode Bitmap (i): Block 1; a bitmap tracking which inodes are free (0) or in-use (1). Data Bitmap (d): Block 2; a bitmap tracking which data blocks are free (0) or allocated (1). Inode Table (I): Blocks 3-7; an array of inodes, where each inode (256 bytes) holds metadata about a file, like size, permissions, and pointers to data blocks. 5 blocks of 4KB will contain 80 256 byte inode strutures. Data Region (D): Blocks 8-63; the largest section, storing the actual contents of files and directories. Inode Every inode has a unique identifier called an inode number (or i-number). This number acts like a file’s address in the file system, allowing the operating system to quickly locate its inode. For example: ...

References 5.6 Problem Generally when traversing the index made up of btree we have to take latch on it. In MySQL 5.6 the approach of taking latch depends on the possible operation we are doing: If the operation is a read operation then taking a read lock is sufficient to prevent any writes to happen to the pages we are accessing in Btree while reading If the operation is a write operation then there are again two possibilities: Optimistic Locking If the write is limited to modifying the leaf page only without modifying the structure of the tree (Merging OR Splitting) then it’s an optimistic locking approach where we take read latch on root of the tree and write latch only on the leaf node to modify ^ab3c53 Pessimistic Locking But if the operation result is in any type of restructuring of the tree itself then that will be known to us only after reaching the target leaf node and knowing its neighbours and parents. So the approach is first to try with optimistic locking defined above and then go for pessimistic locking Pessimistic locking involves taking a write latch on the root resulting in full ownership of the tree by the current operation (until the operation is complete no other operation can take a read or write latch, so all the other operations has to wait even if they are read operations and involve only optimistic locking). When the leaf node is found we take write latch on the leaf’s neighbours as well as its parent and do the restructuring and if the same restructuring needs to happen at parent level then we will take similar write locks recursively up the tree. ^17a3ff ...