Assignment代做 | 代写Sql | 代写Database – 这是基于数据的B+Tree问题
MySQL/InnoDB B+Tree
1
homework
In this assignment, we will look at MySQLs default storage engine: InnoDB. It is internally implemented as B+Tree. In particular, we will witness leaf splitting. And then, we will find out whether InnoDB supports key redistribution and leaf coalescence.
Note that you will submit this homework electronically via Gradiance : http://www.newgradiance.com/services Taking notes while following the instructions and questions in this document will help you solve the problems in Gradiance. However, you do NOT have to submit any cleanly written answers to the questions in this document.
Please start earlier! At least download the necessary files first, even if you plan to work on it later. The virtual machine disk image is large and may take some time to download. Also note that because you need to understand and operate real software, this assignment will take longer than a typical Gradiance homework.
A. Setup
A.1. Downloading
- VirtualBox disk image (64bit) http://www.stanford.edu/class/cs245/data/cs245.vdi.zip (1.3GiB) A smaller 7zip file (856MiB) is also available: replace .zip with .7z from the URL above to download it if you are able to handle 7zip files, or having trouble downloading the larger one. If you are using a 32 bit machine, you may instead need to download the 32 bit vdi from http://www.stanford.edu/class/cs245/data/cs 245 – 32bit.vdi.zip (alternatively extension .7z instead of .zip)
- Other files http://www.stanford.edu/class/cs245/data/cs245-b+tree.zip (11KiB) It includes the files employee_describer.rb , employee_inserts.sql , and seed.sql that are used in this assignment. You might want to download this later within the virtual machine as they will be used inside it.
A. 2 . VirtualBox
After downloading the files, set up a virtual machine using the VirtualBox disk image (cs245.vdi).
1 This assignment was initially created by Dennis Sidharta and revised by Jaeho Shin.
####### Due: Feb 19, 201 7 , 11 :59pm
- Install VirtualBox by downloading the appropriate installer for your machine from
####### https://www.virtualbox.org/wiki/Downloads.
- Create a new virtual machine: a. Start VirtualBox, click the New button, and then enter in the following values
####### Name: cs245 (or whatever name you like)
####### Type: Linux
####### Version: Red Hat (64 bit)
b. If you have a 32 bit machine, use the 32 bit vdi and Red Hat. In some cases
VirtualBox may not show you the 64 bit options even on a 64 bit machine this
can generally be fixed by Enabling Virtualization in your machine BIOS.
Alternatively, you can just use the 32 bit vdi.
####### c. Set other settings like memory size, etc. to your liking.
d. For the hard drive, make sure to point to the provided cs245.vdi.
####### Click Start to launch the virtual machine. To login, use the following username and password:
####### 3. username: root
####### 4. password: cs_
VirtualBoxs Guest Addition has been installed in the virtual machine. Guest Addition adds a few features such as mouse-pointer integration with the host OS, shared folder support, etc.
A. 3 . MySQL
We will be using sql mysql代写”> mysql Comm unity Server version 5.6.10, which has been installed in the virtual
####### machine.
####### Here are various important folders and files that you may need to know:
####### Source location: /root/workspace/mysql-5.6.
####### Installation location: /usr/local/mysql
####### Configuration file: /etc/my.cnf
####### Other files:
/var/lib/mysql/mysql.sock
/var/log/mysqld.log
/var/run/mysqld/mysqld.pid
A. 3 .1. Launching MySQL Server
####### The commands to start and to stop MySQL server are, respectively:
start:
mysqld --debug
####### Due: Feb 19, 201 7 , 11 :59pm
stop:
mysqladmin shutdown
Open a terminal, and then start MySQL server.
A. 3 .2. Launching MySQL Client
On a separate terminal, start a MySQL client by executing mysql -uroot. Once it is started, set the default DB to employee_db by executing use employee_db;
A table named employee has already been set up in the employee_db, whose schema can be checked by executing desc employee;
####### Do not terminate the client for the moment, but if you need to, simply execute exit.
A. 4 . Innodb_ruby
innodb_ruby gem (version 7.6.11) has already been installed in the virtual machine. To check the installation, execute which innodb_space in the command line. Additionally, mysql gem
####### has also been installed.
As mentioned in the readings, when MySQLs innodb_file_per_table configuration is enabled, a tables indexes and its data are stored together in an .idb file. And so, to study InnoDB,
####### we will inspect the contents of /var/lib/mysql/employee_db/employee.idb.
innodb_file_format has already been set to Barracuda, and innodb_file_per_table has already been turned on. To check, execute the following in MySQL client: show global variables like innodb_file%;. If not, you can set them manually by executing the
####### following statements:
SET GLOBAL innodb_file_format = Barracuda; SET GLOBAL innodb_file_per_table = ON;
####### Due: Feb 19, 201 7 , 11 :59pm
####### The following files are included with this assignment:
- seed.sql: This file contains SQL statements to recreate and to reseed employee_dbs tables. In this assignment, you will make changes to the database. And so, if you would like to start over, and thus revert your changes, execute the following command in the terminal: mysql -uroot employee_db < seed.sql (assuming seed.sql is in the
####### directory where you are executing the command)
- employee_inserts.sql: This file contains SQL statements to insert 50 new entries whose ids
####### are between 152 and 250. We will use this later in the assignment.
- employee_describer.rb: Contains an incomplete implementation of a record describer to help innodb_ruby understand employees schema.
Before we start, reset the database to its initial state.
B. Background and Readings
InnoDB uses B+Tree as its index structure. Unlike the B+Tree structure studied in class, however,
####### InnoDB stores the data directly in the trees leaves.
InnoDBs source code is located in /root/workspace/mysql-5.6.10/storage/innobase/. We will not debug or step through the source, but instead we will use innodb_ruby gem to help us explore
####### the internals of InnoDB.
Before proceeding, please read the articles available at the following link: http://www.stanford.edu/class/cs245/homeworks/b+tree/readings/
####### Due: Feb 19, 201 7 , 11 :59pm
1 . B+Tree
Make sure that you are familiar with innodb_spaces three modes: space-page-type- regions, space-index-pages-summary, and index-recurse. And then, answer the
####### following questions:
- Execute the following command: innodb_space -f /var/lib/mysql/employee_db/employee.ibd space- page-type-regions. You may want to redirect the output to a file if you would like to refer to the output again later. How many nodes in total does the tree have, excluding the allocated-but-unused one(s)?
- Complete employee_describer.rb. Hint: one of the readings will teach you how to write and use a record describer for our employee table.
- Do a page-dump on the root node. And, again, you may want to redirect the output to a file. Report the command that you used.
- In that page dump, look at the sizes section. What is the size of a node (i.e., a page), in bytes? Hint: free + used.
- What is the height of the tree? Hint: level.
- How many records are in the root node (and thus the number pages for the leaves)? Hint: n_recs.
- As mentioned in the reading, a record in a non-leaf node has a key and a child_page_number. A key represents the minimum value of the records stored at child_page_number. In addition, among other things, a record also has a pointer to the next record, expressed as an offset within the page. For each record in the root node, report its a. offset, b. key, c. child_page_number, and d. next records relative offset. Note that supremums offset is 112, and thus the last records nexts value is always 112.
- From the answer to the above question, you can easily infer the links between the nodes, e.g. node 8s previous node is 7, while its next node is 11. Another way is to look inside a nodes fil header. Dump node 12, and report the command you used. What are node 12s previous and next nodes?
- Lets have innodb_space recurse the entire tree. Report the command you used. And then, for each leaf node, report a. the number of records, b. the number of bytes occupied for the records, c. minimum key, and d. maximum key
####### Due: Feb 19, 201 7 , 11 :59pm
2 . Leaf Splitting
As you have noticed, most of the nodes are fairly full. Lets add more entries by executing the following command in the terminal:
mysql -uroot employee_db < employee_inserts.sql
####### Afterwards,
- do a page dump on the root node. For each record in the root node, report its a. offset, b. key, c. child_page_number, and d. next records relative offset.
- And then, recurse the entire tree. For each leaf node, report a. the number of records, b. the number of bytes occupied, c. minimum key, and d. maximum key
Notice some of the contents from node 6 have migrated to the previously-unused node 18 to keep the tree balanced. Also, notice that nodes 6 and 7s links have changed to accommodate node 18.
3 . Leaf Coalescence
Before proceeding, reset the databases state, and make sure to insert the records in
####### employee_inserts.sql, just as you did in the previous section (Section 2).
- Delete all records whose ids are between 463 and 753 (inclusive), and thus leaving 5
####### records in node 7. Report the SQL command you used.
####### 2. Recurse the entire tree. For each leaf node, report
####### a. the number of records,
####### b. the number of bytes occupied,
####### c. minimum key, and
####### d. maximum key
####### 3. Does InnoDB support leaf coalescence?
- Repeat 1- 3 for records whose ids are between 1076 and 1357 (inclusive). Deleting those records leaves 10 records in node 11.
####### Due: Feb 19, 201 7 , 11 :59pm
4 . Key Redistribution
Before proceeding, reset the databases state, and make sure to insert the records in
####### employee_inserts.sql, just as you did in Section 2.
####### 1. Delete all records whose ids are between 1359 and 1600 (inclusive), and thus leaving 30
records in node 12, making that node less than half full. Report the SQL command you
used.
- Recurse the entire tree. For each leaf node, report a. the number of records, b. the number of bytes occupied, c. minimum key, and d. maximum key
- Does InnoDB support key redistribution?
- What happens to node 11 when you delete all records whose ids are between 1078 and
####### 1357 (inclusive) instead, and thus leaving 1 1 records in node 11? Repeat 1 – 3.
####### 5. What happens to node 15 if you delete all records whose ids are between 1671 and 1850
####### (inclusive), and thus leaving 61 records in node 1 5? Repeat 1-3.
Notice that your answers to 4 and 5 may vary depending on whether you performed the deletions after resetting the database and inserting the same records, or did it without a reset.
You are encouraged to explore InnoDBs B+Tree leaf coalescence and key redistribution further by deleting different number of records from adjacent leaf nodes in different order. Try to explain why InnoDB resulted in a particular tree structure in terms of support (or lack of support) for leaf coalescence and key redistribution. When unclear, you can always delete records from one node at a time to observe how InnoDB works.